AGC045C Range Set

考虑怎样的 \(x\) 合法，由于之后的操作会覆盖先前的操作，所以正着考虑很复杂，那么正难则反，相当于将长度为 \(a\) 的 0 串覆盖成 ? 表示选择 01 都是合法的

而目标为 0? 组成的串，那么此时一定可以将其覆盖为 ?，那么 01 对称，不妨设 \(a\le b\)

可以发现如果覆盖了一个长度 \(b\) 的 1 段，那么原字符串一定合法，那么合法条件为将每一个长度至少 \(a\) 的 0 段变成 1 后，有长度大于等于 \(b\) 的 1 段

但是此类存在性计数不好 \(\texttt{DP}\)，那么考虑求出不合法的方案数，也就是长度小于 \(a\) 的 0 段将字符串划分成了长度小于 \(b\) 的 01 混合串，且其中 0 的长度大于等于 \(a\)，且两种段的相接点为 1，考虑 \(\texttt{DP}\) 套 \(\texttt{DP}\)，先求出一个 \(f_{i,0/1}\) 表示长度为 \(i\) 的第二种段末尾为 \(0/1\) 的方案数，以此来辅助求出不合法的串，记 \(g_{i,0/1}\) 表示长度为 \(i\) 的不合法串末尾为第一/二种段的方案数，特殊处理一下开头和结尾即可

#include<bits/stdc++.h>
using namespace std;
int n,a,b;
long long s=1,f[5001][2],g[5001][2];
const int mod=1e9+7;
int main(){
	scanf("%d%d%d",&n,&a,&b);
	for(int i=1;i<=n;i++) s=s*2%mod;
	if(a>b) swap(a,b);
	f[0][0]=f[0][1]=g[0][0]=g[0][1]=1;
	for(int i=1;i<b;i++){
		for(int j=0;j<i;j++){
			if(i-j>=a) f[i][0]=(f[i][0]+f[j][1])%mod;
			f[i][1]=(f[i][1]+f[j][0])%mod;
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=0;j<i;j++){
			if(i-j<b) g[i][1]=(g[i][1]+g[j][0]*(i-j-1-(i!=n&&j!=0)<=0?1:f[i-j-1-(i!=n&&j!=0)][0]+f[i-j-1-(i!=n&&j!=0)][1]))%mod;
			if(i-j<a) g[i][0]=(g[i][0]+g[j][1])%mod;
		}
	}
	printf("%lld",(s-g[n][0]-g[n][1]+mod*2)%mod);
	return 0;
}