#include<bits/stdc++.h>
#define LL long long
#define il inline
#define re register
#define inf 2099999999
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define db double
#define eps (1e-5)

using namespace std;
const int N=500000+10,mod=1000000009;
il LL rd()
{
re LL x=0,w=1;re char ch=0;
while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return x*w;
}
int n,f[N],nxt[N],tl,sum;
int to[N],nt[N],hd[N],tot=1;
il void add(int x,int y)
{
if(x<=n) ++tot,to[tot]=y,nt[tot]=hd[x],hd[x]=tot;
}
il void del(int x)
{
for(int i=hd[x];i;i=nt[i])
{
if(to[i]>=tl) sum=(sum-f[to[i]]+mod)%mod;
f[to[i]]=0;
}
}
char cc[N];

int main()
{
scanf("%s",cc+1);
n=strlen(cc+1);
if(n&1) {puts("0");return 0;}
nxt[n]=n+1;
for(int i=n-1;i>=0;i--) nxt[i]=(cc[i+1]=='W')?i+1:nxt[i+1];
for(int i=0;i<=n;i+=2) add((nxt[i]<<1)-i,i);
f[0]=sum=1;
for(int i=2;i<=n;i+=2)
{
del(i);
if(cc[i]=='B') sum=0,tl=i;
else if(cc[i-1]=='B') sum=f[i-2],tl=i-2;
else
{
tl-=2;
if(tl>=0) sum=(sum+f[tl])%mod;
}
sum=(sum+(f[i]=sum))%mod;
}
printf("%d\n",f[n]);
return 0;
}

一个显而易见的动态规划方程用F[i]记录前i位可以得到的不同黑白序列的个数。转移需要考虑所有的j<i，并尝试使j+1到i是一个独立的黑白序列段。总时间复杂度是O(n^2)的，这便可以得到65分。

考虑上述转移中涉及到的j，可以发现需要被考察的j往往是连续的偶数，而其中的断点总会使得对最后一个黑白序列段的长度要求有了两倍以上的限制。所以转移中j的断点只有O(logn)个。用链表维护需要转移的连续若干个j，总的时间复杂度为O(nlogn)，便可以得到满分。

#include<bits/stdc++.h>
#define LL long long
#define il inline
#define re register
#define inf 2099999999
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define db double
#define eps (1e-5)

using namespace std;
const int N=500000+10,mod=1000000009;
il LL rd()
{
re LL x=0,w=1;re char ch=0;
while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return x*w;
}
int n,f[N],nxt[N],tl,sum;
int to[N],nt[N],hd[N],tot=1;
il void add(int x,int y)
{
if(x<=n) ++tot,to[tot]=y,nt[tot]=hd[x],hd[x]=tot;
}
il void del(int x)
{
for(int i=hd[x];i;i=nt[i])
{
if(to[i]>=tl) sum=(sum-f[to[i]]+mod)%mod;
f[to[i]]=0;
}
}
char cc[N];

int main()
{
scanf("%s",cc+1);
n=strlen(cc+1);
if(n&1) {puts("0");return 0;}
nxt[n]=n+1;
for(int i=n-1;i>=0;i--) nxt[i]=(cc[i+1]=='W')?i+1:nxt[i+1];
for(int i=0;i<=n;i+=2) add((nxt[i]<<1)-i,i);
f[0]=sum=1;
for(int i=2;i<=n;i+=2)
{
del(i);
if(cc[i]=='B') sum=0,tl=i;
else if(cc[i-1]=='B') sum=f[i-2],tl=i-2;
else
{
tl-=2;
if(tl>=0) sum=(sum+f[tl])%mod;
}
sum=(sum+(f[i]=sum))%mod;
}
printf("%d\n",f[n]);
return 0;
}

O(n)代码
c++
#include<iostream>
#include<cstdio>
#include<cstring>
#define rep(i,x,y) for(register int i=(x);i<=(y);++i)
#define per(i,x,y) for(register int i=(x);i>=(y);--i)
const int maxn=5e5+10,mo=1e9+9;
typedef long long LL;
using namespace std;
inline int lowbit(int x){return x&(-x);}
inline void ck(int&x){if(x<mo)x+=mo;if(x>=mo)x-=mo;}
inline void ad(int&x,int y){x+=y;ck(x);}
int n,f[maxn];
char s[maxn];
int sum,q;
struct LinkMap{
int tot,head[maxn],to[maxn],next[maxn];
void ins(int a,int b){if(a>n)return;to[++tot]=b;next[tot]=head[a];head[a]=tot;}
void work(int k){
for(int p=head[k];p;p=next[p]){if(to[p]>=q)ad(sum,-f[to[p]]);f[to[p]]=0;}
}
}lp;
int next[maxn];
int main(){
char c=getchar();
while(c=='B'||c=='W'||c=='?')s[++n]=c,c=getchar();
if(n&1){puts("0");return 0;}
next[n]=n+1;per(i,n-1,0)if(s[i+1]=='W')next[i]=i+1;else next[i]=next[i+1];
for(int i=0;i<=n;i+=2)lp.ins(next[i]+next[i]-i,i);
f[0]=1;sum=1;
for(int i=2,j=0;i<=n;i+=2){
lp.work(i-1);lp.work(i);
if(s[i]=='B')j=i,q=i,sum=0;
else if(s[i-1]=='B')j=i-1,q=i-2,sum=f[i-1]+f[i-2],ck(sum);
else ad(sum,(q-1>=0)?f[q-1]:0),ad(sum,(q-2>=0)?f[q-2]:0),q=max(0,q-2);
f[i]=sum;
ad(sum,f[i]);
}
printf("%d",f[n]);
return 0;
}


题目分析
　　一个显而易见的动态规划方程用F[i]记录前i位可以得到的不同黑白序列的个数。转移需要考虑所有的j<i，并尝试使j+1到i是一个独立的黑白序列段。总时间复杂度是O(n^2)的，这便可以得到65分。
　　考虑上述转移中涉及到的j，可以发现需要被考察的j往往是连续的偶数，而其中的断点总会使得对最后一个黑白序列段的长度要求有了两倍以上的限制。所以转移中j的断点只有O(logn)个。用链表维护需要转移的连续若干个j，总的时间复杂度为O(nlogn)，便可以得到满分。

想了很久才想清楚的O(n)算法

#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
using namespace std;

int n;
char s[500005];
int f[500005],head[500005],data[500005],next_list[500005],last_w[500005],next_w[500005];

int mod(int k)
{
if(k<0) k+=1000000009;
else k%=1000000009;
return k;
}
int main(){
int i,j,p,cnt,tmp;
scanf("%s",s+1);
n = strlen(s+1);
p = n+1;
for(i = n;i>=0;i--) {//next_w[i]表示i元素下一个最近的W的位置
next_w[i] = p;
if(s[i]=='W') p = i;
}
p = 0;
for(i = 1;i<=n;i++) {//last_w[i]表示i元素上一个最近的W的位置
last_w[i] = p;
if(s[i]=='W') p = i;
}
memset(head,0,sizeof(head));
cnt=0;
for(i = 1;i<=n;i+=2) {
p = (next_w[i]-i)*2+i+1;
if(last_w[next_w[i]]<i&&p<=n) {
cnt++;
next_list[cnt] = head[p];
head[p] = cnt;
data[cnt] = next_w[i];
}
}
memset(f,0,sizeof(f));
cnt=0;
f[0] = 1;
p = s[1]=='B'?1:0;
for(i = 2;i<=n;i+=2){//f[i]表示1到i有多少种序列,p记录上一个最近的B的位置
if(s[i] == 'B'){
p = i;
cnt = 0;
}
else if(s[i-1] == 'B') {
p = i-1;
cnt = f[i-2];
}
else {
if(s[i-1] != 'W') cnt = mod(cnt+f[i-2]);
for(j = head[i];j!=0;j = next_list[j]){
tmp = data[j]-(i-1-data[j]);
if(0<tmp&&p<data[j]&&last_w[p]<tmp)
cnt = mod(cnt-f[tmp-1]);
}
tmp = p-(i-p)+1;
if(0<tmp&&last_w[p]<tmp) cnt = mod(cnt+f[tmp-1]);
}
f[i] = cnt;
}
printf("%d\n",f[n]);
return 0;
}