果然清华集训的题目。。。显然的DP题但是不会做。。。
我们令f[i][j][w]表示状态方程
w表示到了字符串的第w个
i = 0, 1, 2分别表示k个B和k个W都没填上、k个B填上了k个W没填上、k个B和k个W都填上了三种状态
j = 0, 1分别表示第w位上填B/W
于是方程就比较容易列出来了，注意要用到容斥原理
1 /************************************************************** 2 Problem: 2958 3 User: rausen 4 Language: C++ 5 Result: Accepted 6 Time:652 ms 7 Memory:33032 kb 8 ****************************************************************/ 9 10 #include <cstdio> 11 12 using namespace std; 13 const int N = 1000005; 14 const int mod = 1e9 + 7; 15 16 int n, k; 17 char st[N]; 18 int s0[N], s1[N], f[3][2][N]; 19 20 void read_in() { 21 int i; 22 char ch = getchar(); 23 while (ch != 'W' && ch != 'B' && ch != 'X') 24 ch = getchar(); 25 for (i = 1; i <= n; ++i) 26 st[i] = ch, ch = getchar(); 27 } 28 29 inline int calc(char c, int *s, int i, int t) { 30 if (i < k || st[i - k] == c || s[i] - s[i - k]) return 0; 31 return f[t - 1][i == k ? 0 : 2 - t][i - k]; 32 } 33 34 int main() { 35 int i; 36 scanf("%d%d", &n, &k); 37 read_in(); 38 f[0][0][0] = 1; 39 for (i = 1; i <= n; ++i) { 40 s0[i] = s0[i - 1] + (st[i] == 'W'); 41 s1[i] = s1[i - 1] + (st[i] == 'B'); 42 if (st[i] != 'W') { 43 f[0][0][i] = (0ll + f[0][1][i - 1] + f[0][0][i - 1] - calc('B', s0, i, 1) + mod) % mod; 44 f[1][0][i] = (0ll + f[1][0][i - 1] + f[1][1][i - 1] + calc('B', s0, i, 1)) % mod; 45 f[2][0][i] = (0ll + f[2][0][i - 1] + f[2][1][i - 1]) % mod; 46 } 47 if (st[i] != 'B') { 48 f[0][1][i] = (0ll + f[0][1][i - 1] + f[0][0][i - 1]) % mod; 49 f[1][1][i] = (0ll + f[1][0][i - 1] + f[1][1][i - 1] - calc('W', s1, i, 2) + mod) % mod; 50 f[2][1][i] = (0ll + f[2][0][i - 1] + f[2][1][i - 1] + calc('W', s1, i, 2)) % mod; 51 } 52 } 53 printf("%d ", (f[2][0][n] + f[2][1][n]) % mod); 54 return 0; 55 }
(p.s. Orz 江哥...)