Wannafly Winter Camp 2020-Day6

#include<bits/stdc++.h>
#define pf printf
#define sc(x) scanf("%d", &x)
#define scs(x) scanf("%s", x)
#define scl(x) scanf("%lld", &x)
#define mst(a,x) memset(a, x, sizeof(a))
#define rep(i,s,e) for(int i=s; i<e; ++i)
#define dep(i,e,s) for(int i=e; i>=s; --i)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e5 + 5;
char s[1005];
int main(){
   int _; sc(_); while(_--){
      int n,a,b,c,d; sc(n),sc(a),sc(b),sc(c),sc(d),scs(s);
      int aa=a,bb=b,cc=c,dd=d,mx=0,mn=0; rep(i,0,n){
         if(s[i]=='0'){
            if(dd) dd--,cc++; else if(cc){ } else if(bb) bb--,aa++;
         }
         else{
            if(cc) mx++,cc--; else if(dd) dd--,cc++;
            else if(aa) aa--,mx++; else if(bb) bb--,aa++;
         }
      }
      aa=a,bb=b,cc=c,dd=d; rep(i,0,n){
         if(s[i]=='0'){
            if(cc){ } else if(dd) dd--,cc++;
            else if(aa){ } else if(bb) bb--,aa++;
         }
         else{
            if(dd) dd--,cc++; else if(cc) cc--,mn++;
            else if(bb) bb--,aa++; else if(aa) aa--,mn++;
         }
      } pf("%d %d\n",mx,mn);
   }
}

#include<bits/stdc++.h>
#define scl(x) scanf("%lld", &x)
#define rep(i,s,e) for(int i=s; i<e; ++i)
using namespace std;
typedef long long ll;
ll n,a,b,c,p,d,ans;
vector<int>vv[5005];
int main(){
   scl(n); scl(a); scl(b); scl(c); scl(p); scl(d);
   rep(i,1,n+1) rep(j,1,n+1) if(i!=j&&(a*(i+j)*(i+j)+b*(i-j)*(i-j)+c)%p>d) vv[i].push_back(j);
   rep(i,1,n+1) ans+=vv[i].size()*(n-vv[i].size()-1);
   ans=n*(n-1)*(n-2)/6-ans/2; printf("%lld\n",ans);
}

#include<bits/stdc++.h>
#define pf printf
#define sc(x) scanf("%d", &x)
#define rep(i,s,e) for(int i=s; i<e; ++i)
using namespace std;
const int maxn = 1e5 + 5;
int a[maxn];
int main(){
   int n,cnt(1); sc(n); rep(i,1,n+1){
      if(i&1) a[cnt]=i; else a[n-cnt+1]=i,cnt++;
   } rep(i,1,n+1) pf("%d ",a[i]);
}

#include<bits/stdc++.h>
#define pf printf
#define sc(x) scanf("%d", &x)
#define scs(x) scanf("%s", x)
#define mst(a,x) memset(a, x, sizeof(a))
#define rep(i,s,e) for(int i=s; i<e; ++i)
using namespace std;
char mp[105][105];
int n,m,vis[105][105],ans[105][105];
int dir[8][2]={2,1,2,-1,-2,1,-2,-1,1,2,1,-2,-1,2,-1,-2};
struct node{ int x,y,cnt; }s;
void bfs(){
   ans[s.x][s.y]=0; vis[s.x][s.y]=1;
   queue<node>q; q.push(s); while(!q.empty()){
      node fr=q.front(); q.pop();
      ans[fr.x][fr.y]=fr.cnt; rep(i,0,8){
         node t=fr; t.x+=dir[i][0],t.y+=dir[i][1],t.cnt++;
         if(t.x<0||t.y<0||t.x>=n||t.y>=m) continue;
         if(vis[t.x][t.y]||mp[t.x][t.y]=='X') continue;
         if(mp[fr.x+dir[i][0]/2][fr.y+dir[i][1]/2]=='X') continue;
         q.push(t); vis[t.x][t.y]++;
      }      
   }
}
int main(){
   sc(n); sc(m); rep(i,0,n){
      scs(mp[i]); rep(j,0,m) if(mp[i][j]=='M') s.x=i,s.y=j,s.cnt=0;
   } mst(ans,-1); bfs();
   rep(i,0,n) rep(j,0,m) pf("%d%c",ans[i][j],j==m-1?'\n':' ');
}

#include<bits/stdc++.h>
#define pf printf
#define sc(x) scanf("%d", &x)
#define scs(x) scanf("%s", x)
#define scl(x) scanf("%lld", &x)
#define mst(a,x) memset(a, x, sizeof(a))
#define rep(i,s,e) for(int i=s; i<e; ++i)
#define dep(i,e,s) for(int i=e; i>=s; --i)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 2e5 + 5;
const int mod = 998244353;
int q[105][15][2]; //计数
int vis[105],ac[105]; //vis这个人有没有交过 ac这个人有没有提交过
int sd[15]; //solved
int wa[105][15];
int main(){
   int n,m,w; sc(n); sc(m); sc(w); rep(i,0,w){
      int x,y,c; sc(x); sc(y); sc(c);
      q[x][y][c]++; vis[x]++; if(c){ //如果是ac
         if(q[x][y][0]) wa[x][y]=max(wa[x][y],q[x][y][0]),q[x][y][0]=0;
         ac[x]++; if(q[x][y][1]==1) sd[y]++; //不重复计算ac人数
      }
   } rep(i,1,n+1) rep(j,1,m+1) if(q[i][j][0]) wa[i][j]=max(wa[i][j],q[i][j][0]);
   rep(i,1,n+1){
      if(!vis[i]) puts("998244353"); //没提交
      else if(!ac[i]) puts("1000000"); //爆零
      else{
         int ak(1); rep(j,1,m+1) if(!q[i][j][1]) ak=0;
         if(ak) puts("0"); else{
            //4 有人a自己没a +20
            //5 过半人a自己没a +10
            int ans(0); rep(j,1,m+1) if(!q[i][j][1]&&sd[j]){
               ans+=20; if(sd[j]>=n/2) ans+=10;
            }
            //6 连wa k次 +k^2
            //7 连wa k次且没a +k^2 
            rep(j,1,m+1){
               int k=wa[i][j]; k*=k; ans+=k;
               if(!q[i][j][1]) ans+=k;
            } pf("%d\n",ans);
         }
      }
   }
}

#include<bits/stdc++.h>
#define pf printf
#define sc(x) scanf("%d", &x)
#define rep(i,s,e) for(int i=s; i<e; ++i)
using namespace std;
typedef long long ll;
int a[2005];
int main(){
   int n; ll ans(0); sc(n); rep(i,0,n) sc(a[i]); sort(a,a+n);
   if(n==1) return pf("%d\n",a[0]),0;
   rep(i,0,n-1) ans+=1ll*a[i]*a[i+1],a[i+1]+=a[i];
   pf("%lld\n",ans);
}

#include<bits/stdc++.h>
#define pf printf
#define sc(x) scanf("%d", &x)
#define mst(a,x) memset(a, x, sizeof(a))
#define rep(i,s,e) for(int i=s; i<e; ++i)
#define dep(i,e,s) for(int i=e; i>=s; --i)
using namespace std;
int a[105],ans[105];
int main(){
   int _; sc(_); while(_--){
      int n; sc(n); rep(i,0,n) sc(a[i]);
      int cnt(0),pos(0); mst(ans,0); rep(i,1,n+1){
         while(pos<n&&ans[pos]) pos++;
         if(pos==n) break; if(a[pos]==-1) a[pos]=i;
         dep(j,n-1,pos) if(a[j]==i) ans[j]=++cnt;
      } rep(i,0,n) pf("%d%c",ans[i],i==n-1?'\n':' ');
   }
}

#include<bits/stdc++.h>
#define pf printf
#define sc(x) scanf("%d", &x)
#define scs(x) scanf("%s", x)
#define scl(x) scanf("%lld", &x)
#define mst(a,x) memset(a, x, sizeof(a))
#define rep(i,s,e) for(int i=s; i<e; ++i)
#define dep(i,e,s) for(int i=e; i>=s; --i)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 2e5 + 5;
const int mod = 998244353;
int jc[55],inv[55];
int dp[55],tmp[55];
int q[55][55][55];
int qpow(int x,int y){
   int ans=1; while(y){
      if(y&1) ans=1ll*ans*x%mod; x=1ll*x*x%mod; y>>=1;
   } return ans;
}
int C(int s,int x){
   return 1ll*jc[x]*inv[s]%mod*inv[x-s]%mod;
}
void init(){
   jc[0]=inv[0]=1; rep(i,1,51) jc[i]=1ll*jc[i-1]*i%mod,inv[i]=qpow(jc[i],mod-2);
   rep(i,1,51) rep(j,i,51) rep(k,1,j/i+1) if(k==1) q[i][j][k]=C(i,j);
   else q[i][j][k]=1ll*q[i][j-i][k-1]*C(i,j)%mod;
}
void solve(){
   int n; ll k; sc(n); scl(k); mst(dp,0); dp[0]=1; rep(i,1,n+1){
      if(k%i) continue; memcpy(tmp,dp,sizeof(dp));
      rep(j,0,n+1) for(int t=1,a=jc[i-1];j+t*i<=n;++t,a=1ll*a*jc[i-1]%mod)
         dp[j+t*i]=(1ll*dp[j+t*i]+1ll*tmp[j]*q[i][n-j][t]%mod*a%mod*inv[t])%mod;
   } pf("%d\n",dp[n]);
}
int main(){
   init(); int _; sc(_); while(_--) solve();
}