DP这种东西，考场上就只能看命了。。
#include#include #include #include #include #include using namespace std;typedef long long LL;const int mod=1e9+7;LL f[1100000][3][2];//f[i][j][k]表示第i个位置 j=0没有连续K个的B或W,j=1只有B有,j=2 BW都有 k表示放B还是W int b[1100000],w[1100000];char ss[1100000];int main(){ int n,K; scanf("%d%d",&n,&K); scanf("%s",ss+1); for(int i=1;i<=n;i++) { b[i]=b[i-1];w[i]=w[i-1]; if(ss[i]=='B')b[i]++; else 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]=='B'||ss[i]=='X') { f[i][0][0]=(f[i][0][0]+(f[i-1][0][0]+f[i-1][0][1])%mod)%mod; f[i][1][0]=(f[i][1][0]+(f[i-1][1][0]+f[i-1][1][1])%mod)%mod; f[i][2][0]=(f[i][2][0]+(f[i-1][2][0]+f[i-1][2][1])%mod)%mod; } if(ss[i]=='W'||ss[i]=='X') { f[i][0][1]=(f[i][0][1]+(f[i-1][0][0]+f[i-1][0][1])%mod)%mod; f[i][1][1]=(f[i][1][1]+(f[i-1][1][0]+f[i-1][1][1])%mod)%mod; f[i][2][1]=(f[i][2][1]+(f[i-1][2][0]+f[i-1][2][1])%mod)%mod; } if(i