BZOJ 2958&3269: 序列染色 December 26, 2016 ###Description 给出一个长度为N由B、W、X三种字符组成的字符串S，你需要把每一个X染成B或W中的一个。 对于给出的K，问有多少种染色方式使得存在整数a,b,c,d使得: 1<=a<=b<c<=d<=N Sa,Sa+1,...,Sb均为B Sc,Sc+1,...,Sd均为W 其中b=a+K-1,d=c+K-1 由于方法可能很多，因此只需要输出最后的答案对109+7取模的结果。 ###Input 第一行两个正整数N,K 第二行一个长度为N的字符串S ###Output 一行一个整数表示答案%(109+7)。 ###Sample Input 5 2 XXXXX ###Sample Output 4 ###Solution 首先搞出B和W的前缀个数，那么可以O(1)判某段区间能否为B或W 然而这样对于超过K个的会算重 对于连续的B和W，考虑用最后K个计算，则不会算重（可以在序列最后加一个X，更好写） 状态可以设计成f[i][j][k]表示考虑前i位，状态为j，这一位选了k，j为0,1,2分别代表BW都没有，只有B，BW都有 转移看代码 ###Code ```c++ #include<bits/stdc++.h> #define mod 1000000007 int n,k,bp[1000010],wp[1000010],f[1000010][3][2]; char s[1000010]; int main() { scanf("%d%d%s",&n,&k,s+1); s[++n]='X'; for(int i=1;i<=n;i++) { bp[i]=bp[i-1]+(s[i]=='B'); wp[i]=wp[i-1]+(s[i]=='W'); } f[0][0][0]=1; for(int i=1;i<=n;i++) { if(s[i]=='B'||s[i]=='X') for(int j=0;j<3;j++)f[i][j][0]=(f[i-1][j][0]+f[i-1][j][1])%mod; if(s[i]=='W'||s[i]=='X') for(int j=0;j<3;j++)f[i][j][1]=(f[i-1][j][0]+f[i-1][j][1])%mod; if(i<=k)continue; if((s[i]=='B'||s[i]=='X')&&!(bp[i-1]-bp[i-k-1])) { f[i][2][0]=(f[i][2][0]+f[i-k][1][1])%mod; f[i][1][0]=(f[i][1][0]-f[i-k][1][1])%mod; } if((s[i]=='W'||s[i]=='X')&&!(wp[i-1]-wp[i-k-1])) { f[i][1][1]=(f[i][1][1]+f[i-k][0][0])%mod; f[i][0][1]=(f[i][0][1]-f[i-k][0][0])%mod; } } int ans=f[n][2][0]; if(ans<0)ans+=mod; printf("%d\n",ans); } ```