链接：https://www.luogu.com.cn/problem/P6212
题目描述：有一个串，每个字符为\(A,B,?\)中的一个。
\(?\)会是\(A,B\)中等概率随机的一个字符，若有一个点为\(A\)，其后面的点为\(B\)，满意度会加\(-b\)，若有一个点为\(B\)，其后面的点为\(A\)，满意度会加\(a\)。
求满意度\(<=m\)的概率。
题解：可以发现，产生贡献当且仅当该位置在\(A\)连通块与\(B\)连通块之间，而\(A\)连通块个数与\(B\)连通块个数个数的差的绝对值小于等于\(1\)，而且与第一个元素与最后一个元素的取值相关，所以我们可以\(dp\)\(A,B\)分界线数，然后推出
\(B,A\)分界线数。
令\(dp_{i,j,0/1,0/1}\)表示第\(i\)个点，有\(j\)个\(A,B\)分界线，开端点为\(A\)或\(B\)，末尾点为\(A\)或\(B\)的方案数。
则枚举\(?\)填什么然后转移可算出方案数，除以总方案数可得到答案。
当然此题空间限制过小，需要滚动数组优化。
#include<iostream>
#define mod 1000000007
using namespace std;
long long n,m,a,b,t,sum,type,dp[2][2021][2][2];
char s[2021];
long long fast_pow(long long a,int b)
{
if (b==0)
return 1;
if (b&1)
return fast_pow(a*a%mod,b/2)*a%mod;
else
return fast_pow(a*a%mod,b/2);
}
int main()
{
cin>>n>>m>>a>>b;
for (int i=1;i<=n;++i)
{
cin>>s[i];
if (s[i]=='?')
t++;
}
if (s[1]!='B')
dp[0][0][1][1]=1;
if (s[1]!='G')
dp[0][0][0][0]=1;
for (int i=2;i<=n;++i)
{
type^=1;
for (int j=0;j<=n;++j)
dp[type][j][0][0]=dp[type][j][0][1]=dp[type][j][1][0]=dp[type][j][1][1]=0;
for (int j=0;j<=n;++j)
for (int k=0;k<=1;++k)
{
if (s[i]!='B')
{
if (j>=1)
dp[type][j][1][k]=(dp[type][j][1][k]+dp[type^1][j-1][0][k])%mod;
dp[type][j][1][k]=(dp[type][j][1][k]+dp[type^1][j][1][k])%mod;
}
if (s[i]!='G')
{
dp[type][j][0][k]=(dp[type][j][0][k]+dp[type^1][j][1][k])%mod;
dp[type][j][0][k]=(dp[type][j][0][k]+dp[type^1][j][0][k])%mod;
}
}
}
for (int i=0;i<=n;++i)
{
if (i*a-i*b>=m)
sum=(sum+dp[type][i][1][1]+dp[type][i][0][0])%mod;
if (i>0&&(i-1)*a-i*b>=m)
sum=(sum+dp[type][i][1][0])%mod;
if ((i+1)*a-i*b>=m)
sum=(sum+dp[type][i][0][1])%mod;
}
cout<<sum*fast_pow(fast_pow(2,t),mod-2)%mod<<endl;
return 0;
}