【动态规划】美妙的歌声

设f[i][0/1]为唱到第i位，结尾为0/1（da为0，do为1）
枚举上一段最后的位置，其答案*2的中间s个数次方的累加和为结果

#include
#include
#include
using namespace std;
string s;
int n,l,r,a[5010];
long long power[5010],f[5010][3],mo;
int main()
{
	freopen("listen.in","r",stdin);
	freopen("listen.out","w",stdout);
	cin>>s;
	n=s.size();
	scanf("%d%d%lld",&l,&r,&mo);
	power[0]=1;
	f[0][0]=f[0][1]=1;
	for (int i=0;i
		if (s[i]=='S') a[i+1]+=a[i]+1;
		   else a[i+1]=a[i];
		power[i+1]=power[i]*2%mo;
	}
	for (int i=1;i<=n;i++)
	    for (int j=max(0,i-r);j<=i-l;j++)
	    {
	    	f[i][0]=(f[i][0]+f[j][1]*power[a[i-1]-a[j]]%mo)%mo;
	    	if (a[i]-a[i-1]) f[i][1]=(f[i][1]+f[j][0]*power[a[i-1]-a[j]]%mo)%mo;  //此位置上是s才能唱do 
		}
	printf("%lld",(f[n][0]+f[n][1])%mo);
	return 0;
}