bzoj_3269 序列染色

题目:

  给出一个长度为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
  由于方法可能很多,因此只需要输出最后的答案对10^9+7取模的结果。

思路:

  设 表示第 个点,颜色为 ,现在在第 个阶段。
  但是最终的方法不一定只有一段长度为 的 B 和 W。因此如果每次直接根据 这个区间是否合法转移是会出现重复的。一个比较常规的想法就是:只要凑齐 个 W/B,就必须进入下一个阶段(也就是说每个状态都从最前面的 个连续的去转移),显然这样是不重不漏的。所以当能从 阶段转入 时,一定要在 阶段中减去这些状态(转移见代码)。

代码:

#include <bits/stdc++.h>
#define ALL(x) x.begin(), x.end()
#define mset(a, b) memset(a, b, sizeof a)
#define rep(i, a, b) for(int i(a), i##_END_(b); i <= i##_END_; i++) 
#define drep(i, a, b) for(int i(a), i##_END_(b); i >= i##_END_; i--)
template<class T> inline bool tomax(T &a, T b) {return a < b ? a = b, 1 : 0;}
template<class T> inline bool tomin(T &a, T b) {return b < a ? a = b, 1 : 0;}
typedef long long ll;

const int N = 1e6 + 5, MOD = 1e9 + 7;

char s[N];
int dp[N][3][2], sb[N], sw[N];

int main() {
    // freopen("data.in", "r", stdin);
    int n, k;
    scanf("%d%d", &n, &k);
    scanf("%s", s + 1);
    rep(i, 1, n) {
        sb[i] = sb[i - 1] + (s[i] == 'B');
        sw[i] = sw[i - 1] + (s[i] == 'W');
    }
    dp[0][0][1] = 1;
    rep(i, 1, n) {
        rep(k, 0, 2) {
            int tmp = (dp[i - 1][k][0] + dp[i - 1][k][1]) % MOD;
            if(s[i] != 'W') (dp[i][k][0] += tmp) %= MOD;
            if(s[i] != 'B') (dp[i][k][1] += tmp) %= MOD;
        }
        if(i < k) continue;
        if(s[i] != 'W' && sw[i] == sw[i - k]) {
            (dp[i][1][0] += dp[i - k][0][1]) %= MOD;
            (dp[i][0][0] -= dp[i - k][0][1]) %= MOD;
        }
        if(s[i] != 'B' && sb[i] == sb[i - k]) {
            (dp[i][2][1] += dp[i - k][1][0]) %= MOD;
            (dp[i][1][1] -= dp[i - k][1][0]) %= MOD;
        }
    }
    int ans = (dp[n][2][0] + dp[n][2][1]) % MOD;
    printf("%d\n", (ans + MOD) % MOD);
    return 0;
}