bzoj2958 序列染色

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
数据约定
　　对于20%的数据，N<=20
　　对于50%的数据，N<=2000
　　对于100%的数据，1<=N<=10^6，1<=K<=10^6

正解：$dp$。

神$dp$神状态系列，蒟蒻根本想不到。。

设$f[i][j][k]$表示当前搞到序列第$i$位，$j$为$0$表示没有连续$k$个$B$，$j$为$1$表示已经有连续$k$个$B$，但没有连续$k$个$W$，$j$为$2$表示有连续$k$个$B$和连续$k$个$W$，$k$为$0$表示这一位为$B$，$k$为$1$表示这一位为$W$。

直接转移，注意在能恰好产生$k$个$B$或$W$时，加上漏算的答案，减去重复的答案即可。

话说当时在$win7$下的$emacs$做这题有一个$W$写成$w$还看不出来。。

 1 #include <bits/stdc++.h>
 2 #define il inline
 3 #define RG register
 4 #define ll long long
 5 #define N (1000010)
 6 #define rhl (1000000007)
 7  
 8 using namespace std;
 9  
10 int f[N][3][2],sb[N],sw[N],n,k;
11 char s[N];
12  
13 il void upd(RG int &v,RG int x,RG int y,RG int z){
14   v=x+y; if (v>=rhl) v-=rhl; v+=z;
15   if (v>=rhl) v-=rhl; return;
16 }
17  
18 int main(){
19 #ifndef ONLINE_JUDGE
20   freopen("color.in","r",stdin);
21   freopen("color.out","w",stdout);
22 #endif
23   cin>>n>>k,scanf("%s",s+1);
24   for (RG int i=1;i<=n;++i){
25     sb[i]=sb[i-1],sw[i]=sw[i-1];
26     if (s[i]=='B') ++sb[i];
27     if (s[i]=='W') ++sw[i];
28   }
29   f[0][0][1]=1;
30   for (RG int i=1,tmp;i<=n;++i){
31     if (s[i]!='W'){
32       if (i>=k && s[i-k]!='B' && sw[i]==sw[i-k]) tmp=f[i-k][0][1]; else tmp=0;
33       upd(f[i][0][0],f[i-1][0][0],f[i-1][0][1],rhl-tmp);
34       upd(f[i][1][0],f[i-1][1][0],f[i-1][1][1],tmp);
35       upd(f[i][2][0],f[i-1][2][0],f[i-1][2][1],0);
36     }
37     if (s[i]!='B'){
38       if (i>=k && s[i-k]!='W' && sb[i]==sb[i-k]) tmp=f[i-k][1][0]; else tmp=0;
39       upd(f[i][0][1],f[i-1][0][0],f[i-1][0][1],0);
40       upd(f[i][1][1],f[i-1][1][0],f[i-1][1][1],rhl-tmp);
41       upd(f[i][2][1],f[i-1][2][0],f[i-1][2][1],tmp);
42     }
43   }
44   cout<<(f[n][2][0]+f[n][2][1])%rhl; return 0;
45 }