本番中にどうにか解いたけど、だいぶ苦戦してる。
https://codeforces.com/contest/2129/problem/D
問題
1~NのPermutation Pがあったとき、以下の要領でN要素のスコア配列Sを定める。
N個のセルが一列に並んでおり、初期状態ですべて白色である。
- 以下をNターン行う。
- 2ターン目以降、iターンにはセルP[i]に最も近い黒色のセル番号をjとしたとき、S[j]をインクリメントする。
- iターン目はセルP[i]を黒く塗る。
最終的なSが与えられる。
ただし一部の値は不定である。
そのようなSを構築できるPは何通りか。
解法
各セルが得るスコアの最大はO(logN)である。
f(L,ls,R,rs) := Sの区間[L,R]に対し、S[L]=ls、S[R]=rsとなるような[L...R]の彩色順
として区間の短い順にDPをしていこう。
int T,N; const int DI=12; ll memoL[101][DI+1]; ll memoR[101][DI+1]; ll memo[101][DI+1][101][DI+1]; int A[101]; const ll mo=998244353; ll comb(int P_,int Q_) { static const int N_=1020; static ll C_[N_][N_]; if(C_[0][0]==0) { int i,j; FOR(i,N_) C_[i][0]=C_[i][i]=1; for(i=1;i<N_;i++) for(j=1;j<i;j++) C_[i][j]=(C_[i-1][j-1]+C_[i-1][j])%mo; } if(P_<0 || P_>N_ || Q_<0 || Q_>P_) return 0; return C_[P_][Q_]; } /* ll dfsL(int cur,int num); ll dfsR(int cur,int num); ll dfs(int L,int Lnum,int R,int Rnum); ll dfsL(int cur,int num) { if(cur==0) return num==0; if(num<=0) return 0; if(num>cur) return 0; int req=1<<(num-1); if(req>cur) return 0; if(memoL[cur][num]>=0) return memoL[cur][num]; ll ret=0; int i,x,y; FOR(i,cur) { FOR(x,DI+1) FOR(y,DI+1) if(x+y<=DI&&(A[i]==-1||A[i]==x+y)) { ret+=dfsL(i,x)*dfs(i,y,cur,num-1)%mo*comb(cur-1,i)%mo; } } return memoL[cur][num]=ret%mo; } ll dfsR(int cur,int num) { if(cur==N-1) return num==0; if(num<=0) return 0; if(num>N-1-cur) return 0; int req=1<<(num-1); if(req>N-cur-1) return 0; if(memoR[cur][num]>=0) return memoR[cur][num]; ll ret=0; int i,x,y; for(i=cur+1;i<N;i++) { FOR(x,DI+1) FOR(y,DI+1) if(x+y<=DI&&(A[i]==-1||A[i]==x+y)) { ret+=dfsR(i,x)*dfs(cur,num-1,i,y)%mo*comb(N-cur-2,N-1-i)%mo; } } return memoR[cur][num]=ret%mo; } ll dfs(int L,int Lnum,int R,int Rnum) { if(Lnum<0||Rnum<0) return 0; if(Lnum+Rnum>R-L-1) return 0; if(L+1==R) return (Lnum+Rnum==0); if(Lnum+Rnum==0) return 0; if(Lnum==0) return 0; int req=1<<(Lnum-1); if(Rnum) req+=1<<(Rnum-1); if(req>R-L) return 0; if(memo[L][Lnum][R][Rnum]>=0) return memo[L][Lnum][R][Rnum]; ll ret=0; int i,x,y; for(i=L+1;i<R;i++) { FOR(x,DI+1) FOR(y,DI+1) if(x+y<=DI&&(A[i]==-1||A[i]==x+y)) { if((i-L)<=(R-i)) { ret+=dfs(L,Lnum-1,i,x)*dfs(i,y,R,Rnum)%mo*comb(R-L-2,R-i-1)%mo; } else { ret+=dfs(L,Lnum,i,x)*dfs(i,y,R,Rnum-1)%mo*comb(R-L-2,R-i-1)%mo; } } } return memo[L][Lnum][R][Rnum]=ret%mo; } */ void solve() { int i,j,k,l,r,x,y; string s; cin>>T; while(T--) { cin>>N; FOR(i,N) cin>>A[i]; FOR(x,N) { FOR(i,DI+1) { memoL[x][i]=memoR[x][i]=0; FOR(y,N) FOR(j,DI+1) memo[x][i][y][j]=0; } } ll ret=0; int num; for(int len=1;len<=N;len++) { if(len==2) { FOR(x,N-1) memo[x][0][x+1][0]=1; } else if(len>=3) { for(int L=0;L+len<=N;L++) { int R=L+len-1; for(int Lnum=1;Lnum<=DI;Lnum++) for(int Rnum=0;Rnum<=DI;Rnum++) { int req=1<<(Lnum-1); if(Rnum) req+=1<<(Rnum-1); if(req>R-L) continue; int i,x,y; ll ret=0; for(i=L+1;i<R;i++) { ll pat=0; if(1<<(Lnum-1)>i-L+1) continue; if(Rnum&&1<<(Rnum-1)>R-i+1) continue; FOR(x,DI+1) { int req=0; if(x) req+=1<<(x-1); if(req>i-L+1) break; FOR(y,DI+1) if(x+y<=DI&&(A[i]==-1||A[i]==x+y)) { int req=0; if(y) req+=1<<(y-1); if(req>R-i+1) break; if((i-L)<=(R-i)) { pat+=memo[L][Lnum-1][i][x]*memo[i][y][R][Rnum]%mo; } else { if(Rnum) pat+=memo[L][Lnum][i][x]*memo[i][y][R][Rnum-1]%mo; } } } ret+=pat%mo*comb(R-L-2,R-i-1)%mo; } memo[L][Lnum][R][Rnum]=ret%mo; } } } if(len==1) { memoL[0][0]=memoR[N-1][0]=1; } else { FOR(num,7+1) if(num) { int cur=len-1; FOR(i,cur) { ll pat=0; FOR(x,7+1) FOR(y,DI+1) if(x+y<=DI&&(A[i]==-1||A[i]==x+y)) { (pat+=memoL[i][x]*memo[i][y][cur][num-1])%=mo; } (memoL[cur][num]+=pat%mo*comb(cur-1,i))%=mo; } cur=N-len; for(i=cur+1;i<N;i++) { ll pat=0; FOR(x,7+1) FOR(y,DI+1) if(x+y<=DI&&(A[i]==-1||A[i]==x+y)) { (pat+=memoR[i][x]*memo[cur][num-1][i][y])%=mo; } (memoR[cur][num]+=pat%mo*comb(N-cur-2,N-1-i))%=mo; } } } } FOR(i,N) { FOR(x,DI+1) FOR(y,DI+1) if(x+y<=DI&&(A[i]==-1||A[i]==x+y)) { (ret+=memoL[i][x]*memoR[i][y]%mo*comb(N-1,i))%=mo; } } cout<<ret%mo<<endl; } }
まとめ
途中色々実験したりして手間取った。