注:本题解中下标从1开始

这题可以想出一个\(O(n^2)\)的dp,只要考虑每个偶数位置可以从前面的哪个位置加上一个"B...W..."转移过来

然而数据范围有5e5,,,

打表找规律(误),可以发现转移的时候,能够转移位置构成的集合可能会向前多一个元素,向后多一个元素,或者中间少掉一些或全部元素

简化问题,如果现在在\(i\)位置有一个W,同时前面的\(j\)位置到\(i\)之间没有W,那么在往后转移的过程中,如果转移到了\(2i-j\),那么\(j\)就无法向后贡献答案了

就像这样

可以发现因为\(i\)位置为W,所以\(j\)最多只能贡献到位置\(2i-j-2\)

所以求出每个位置\(j\)后面最近的W位置\(i\),然后在\(2i-j\)处像存图一样跟\(j\)连边

转移的时候,用一个变量\(sum\)存储能够转移的所有\(f_j\)之和,如果当前位置为B就无法转移,否则如果前一个位置为B就只能从这个位置往前两个的位置转移过来,其他情况,用一个指针\(tl\)表示当前转移区间的左端点,每次往左移动加入答案;还要记得把该位置所连出去的点,也就是无法贡献答案位置贡献扣除,每次把\(f_i\)加到\(sum\)里去

这里参考了之前大佬的思路和代码

// luogu-judger-enable-o2#include
    
     #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;}