# Bzoj2958 & 3269: sequence staining (DP)

2020-12-07 15:04:43

Subject portal
Metaphysics can't really .

solution ：
f[i][j][k] It means the first one i position ,k=0 fill B,k=1 fill W.
j=0 The length of a paragraph is K Successive B None .
j=1 There is a paragraph with the length of K Successive B.
j=2 There is a paragraph with the length of K Successive W.
Because you have to have B It's continuous W continuity .
that j=2 Definitely from j=1 Transfer

Keep it continuous B There must be one behind W, Successive W There's a B, The answer is f[n+1][2][0]
Suppose this one chooses B Obviously there is
f[i][j][0]=f[i-1][j][1]+f[i-1][j][0]
if(i-k+1 To i No, W)f[i][1][0]=f[i][1][0]+f[i-k][0][1];
But there will be repetition , because f[i][0][0] It's a random shift , There may already be B 了 , therefore :
if(i-k+1 To i No, W)f[i][0][0]=f[i][0][0]-f[i-k][0][1];

Code implementation ：

``````#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<queue>
#include<cmath>
using namespace std;
int b[1110000],w[1110000],f[1110000][3][2];char ss[1110000];
const int mod=1000000007;
int main() {
int n,k;scanf("%d%d%s",&n,&k,ss+1);
ss[++n]='X';memset(b,0,sizeof(b));memset(w,0,sizeof(b));
for(int i=1;i<=n;i++) {
b[i]=b[i-1];if(ss[i]=='B')b[i]++;
w[i]=w[i-1];if(ss[i]=='W')w[i]++;
}
memset(f,0,sizeof(f));f[0][0][1]=1;
for(int i=1;i<=n;i++) {
if(ss[i]!='W')for(int j=0;j<3;j++)f[i][j][0]=(f[i-1][j][0]+f[i-1][j][1])%mod;
if(ss[i]!='B')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(ss[i]!='W'&&w[i]==w[i-k]) {
f[i][1][0]=(f[i][1][0]+f[i-k][0][1])%mod;
f[i][0][0]=(f[i][0][0]-f[i-k][0][1])%mod;
}if(ss[i]!='B'&&b[i]==b[i-k]) {
f[i][2][1]=(f[i][2][1]+f[i-k][1][0])%mod;
f[i][1][1]=(f[i][1][1]-f[i-k][1][0])%mod;
}
}printf("%d\n",((f[n][2][0])%mod+mod)%mod);
return 0;
}``````

https://chowdera.com/2020/12/202012071504368615.html