0%

AGC045C Range Set

发表于 阅读次数： Valine：

题目链接

首先，我们发现交换 \(A\) 和 \(B\) 的值答案是不变的，因为显然我们可以把序列变为全 \(1\)，那么对于每一种未交换 \(AB\) 的合法序列，每一位全部反转后得到的序列一定可以在交换 \(AB\) 后得到。所以下面我们假定 \(A\leqslant B\)。

我们考虑给定一个序列，如何判断其是否可以被得到。

首先我们发现，如果这个序列把所有长度大于等于 \(A\) 的全部为 \(0\) 的子串置为 \(1\) 后，存在一个长度大于等于 \(B\) 的全部为 \(1\) 的子串，那么它可以被得到。因为我们可以按照从外向内的方式得到这个子串外的每一位，并且都不会影响其它子串外的位，然后把这个子串全部置为 \(1\)。这样就得到了变化后的序列，再把变为 \(1\) 的部分置为 \(0\) 即可。

必要性可以考虑全部置为 \(1\) 的操作，如果不存在长度大于等于 \(B\) 的全 \(1\) 子串，那么任何一个置 \(1\) 操作都会让至少一个 \(0\) 变成 \(1\)，而任何一个置 \(0\) 操作也会让至少一个 \(1\) 变成 \(0\)，所以怎么调整都无法结束。

现在我们考虑计算答案，我们计算不可以被得到的序列的个数，即把所有长度大于等于 \(A\) 的纯 \(0\) 子串置为 \(1\) 后，不存在长度大于等于 \(B\) 的纯 \(1\) 子串，再用 \(2^n\) 减去即可。

设 \(f(i,0/1)\) 为长度为 \(i\)，最后一位为 \(0/1\)（注意这里如果最后是连续的长度大于等于 \(A\) 的 \(0\) 串除了在结尾我们都不计算） 的不合法的序列个数，为了计算 \(f\)，我们再引入 \(g(i,0/1)\) 为长度为 \(i\)，所有极大 \(0\) 子串的长度均大于等于 \(A\)，且第一位为 \(1\)，最后一位为 \(0/1\) 的序列的个数。

先考虑 \(g\) 的转移，考虑最后放的是 \(1\) 还是连续的一段 \(0\)，我们有： \[ g(i,0)=\sum\limits_{j\leqslant i-A}g(j,1)\\ g(i,1)=g(i-1,0)+g(i-1,1) \] 然后考虑 \(f\)，我们需要每一次填一段长度小于 \(B\) 且头尾都是 \(1\) 的 \(g\) 表示的序列或者一段长度小于 \(A\) 的 \(0\)，为了防止两段的 \(0\) 在一起，我们限制了头尾都是 \(1\)，但是在最终的序列的头尾是没有这个限制的，所以我们需要额外加上一部分答案，则我们有 \[ f(i,0)=\sum\limits_{j>i-A}f(j,1)+[i=n]\sum\limits_{j>i-B}f(j,0)g(i-j,0)\\ f(i,1)=\sum\limits_{j>i-B}f(j,0)(g(i-j,1)+[j=0]g(i-j,0)) \] 注意最后一个 \(g(i-j,0)\) 指的是以 \(0\) 开头，\(1\) 结尾的串（也就是把所有串反过来）。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<bits/stdc++.h>
using namespace std;
int const p=1e9+7;
int f[5005][2],g[5005][2];
int mod(int x){return x>=p?x-p:x;}
int main()
{
    int n,a,b;
    scanf("%d%d%d",&n,&a,&b);
    if(a>b)swap(a,b);
    g[1][1]=1;
    for(int i=2;i<b;i++)
    {
        for(int j=1;j<=i-a;j++)
            g[i][0]=mod(g[i][0]+g[j][1]);
        g[i][1]=mod(g[i-1][0]+g[i-1][1]);
    }
    f[0][0]=f[0][1]=1;
    for(int i=1;i<=n;i++)
    {
        for(int j=max(i-a+1,0);j<i;j++)f[i][0]=mod(f[i][0]+f[j][1]);
        for(int j=max(i-b+1,0);j<i;j++)
        {
            if(i==n)f[i][0]=(f[i][0]+1ll*f[j][0]*g[i-j][0])%p;
            if(j==0)f[i][1]=(1ll*f[i][1]+g[i][0]+g[i][1])%p;
            else f[i][1]=(f[i][1]+1ll*f[j][0]*g[i-j][1])%p;
        }
    }
    int pw=1;
    for(int i=1;i<=n;i++)pw=mod(pw+pw);
    printf("%lld",(1ll*pw+p+p-f[n][0]-f[n][1])%p);
    return 0;
}