[atAGC045C]Range Set

首先我们可以把所有位置都变为1，因此不妨假设$a\le b$

一个字符串$s$合法当且仅当：将其中每一段长度不小于$a$的0变成1后，存在一段1的长度都不小于$b$

证明：我们称$S_{a,b}$为通过$(a,b)$能产生的字符串所构成的集合，则有$S_{a,b}=S_{b,a}$

称原来的字符串为$s$，将每一段长度不小于$a$的0变成1后称为$s'$，则若$s'\in S_{a,b}$则可以得到$s\in S_{a,b}$，同时若有$s\in S_{b,a}$又可以得到$s'\in S_{b,a}$，即可得$s\in S_{a,b}$等价于$s'\in S_{a,b}$

接下来，就是证明$s'\in S_{a,b}$当且仅当存在一段1的长度都不小于$b$

必要性：考虑$s'$中不存在一段0的长度不小于$a$，又不存在一段1的长度不小于$b$，对最后一次操作分类讨论即可（初始$n\ge a,b$，也满足条件）

充分性：将长度不小于$b$的一段1变为0，则若可以得到这个串则一定可以得到$s'$，然后由于$b\ge a$，再把这段0和左右两边原来的0合并起来，长度不小于$a$，根据上面的结论，可以将这一段变为1

重复此操作，每一次操作必然减少一段0，因此最终即所有位置都为1，显然可以做到

统计不合法的字符串数量，假设已经确定$s'$，去统计对应为$s'$的$s$数量，考虑dp

预处理出用$g_{l}$表示将这段1中若干个位置改为0，且每一段0的长度都不小于$a$的方案数，再用用$f_{i,0/1}$表示前$i$个数，第$i$个数为0或1，简单转移即可

 1 #include<bits/stdc++.h>

 2 using namespace std;

 3 #define N 5005

 4 #define mod 1000000007

 5 int n,a,b,ans,g[N],f[N][N];

 6 int main(){

 7     scanf("%d%d%d",&n,&a,&b);

 8     if (a>b)swap(a,b);

 9     for(int i=0;i<a;i++)g[i]=1;

10     for(int i=a;i<=n;i++){

11         g[i]=(g[i-1]+1)%mod;

12         for(int j=a;j<i;j++)g[i]=(g[i]+g[i-j-1])%mod;

13     }

14     f[0][0]=f[0][1]=1;

15     for(int i=1;i<=n;i++)

16         for(int j=0;j<i;j++)

17             if (i-j<b){

18                 int l=i-j-2;

19                 if (!j)l++;

20                 if (i==n)l++;

21                 f[i][1]=(f[i][1]+1LL*f[j][0]*g[max(l,0)])%mod;

22                 if (i-j<a)f[i][0]=(f[i][0]+f[j][1])%mod;

23             }

24     ans=1;

25     for(int i=0;i<n;i++)ans=ans*2%mod;

26     ans=(ans+mod-(f[n][0]+f[n][1])%mod)%mod;

27     printf("%d",ans);

28 }

巴特西

[atAGC045C]Range Set

最新文章

热门文章