頭がこんがらがる。
http://arc065.contest.atcoder.jp/tasks/arc065_d
問題
01で構成されたN文字の文字列Sがある。
ここに以下のM個のクエリが与えられる。
各クエリiは区間[L[i],R[i]]で構成され、S[L[i]...R[i]]を任意にシャッフルできることを意味する。
L[i]は非減少である。
最終的に得られる文字列の組み合わせを求めよ。
解法
尺取り法の要領で解く。
dp(x,y) := Sのx文字目までに0がy回出てくるような組み合わせの数
x+1文字目を0にするか1にするかを考える。
x+1∈(L[i],R[i])となるようなクエリにおけるR[i]の最大値をMR(x+1)とする。
x+1文字目には、SのうちMR(x+1)文字目までのいずれかの文字を持ってこれる。
MR(x+1)文字目までの0,1の登場回数と、x文字目までの0,1の登場回数がわかっていれば、x+1文字目に0,1をそれぞれ配置可能かわかる。
あとはDPでdp(x,y)を更新していき、dp(N,S中の0の数)を答えればよい。
int N,M; string S; ll mo=1000000007; ll dp[3030][3030]; void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>M>>S; int CR=0,CL=0; int B[2]={}; dp[0][0]=1; while(M--) { int L,R; cin>>L>>R; L--,R--; while(CL<L) { if(CL==CR) B[S[CR++]=='1']++; FOR(i,3001) if(dp[CL][i]) { if(i<B[0]) (dp[CL+1][i+1]+=dp[CL][i])%=mo; if(CL-i<B[1]) (dp[CL+1][i]+=dp[CL][i])%=mo; } CL++; } while(CR<=R) B[S[CR++]=='1']++; } while(CL<N) { if(CL==CR) B[S[CR++]=='1']++; FOR(i,3001) if(dp[CL][i]) { if(i<B[0]) (dp[CL+1][i+1]+=dp[CL][i])%=mo; if(CL-i<B[1]) (dp[CL+1][i]+=dp[CL][i])%=mo; } CL++; } cout<<dp[CL][B[0]]<<endl; }
まとめ
こちらの方がコードは単純。