CF585F Digits of Number Pi 题解

绝顶我为峰 · 2022-08-01 12:51:12 · 题解

虚假的 *3200?

真实的 *2300!

把 s 的所有后缀建一个 AC 自动机，对每个点求出深度之后，一个串的匹配可以看做在 AC 自动机上走，这个串出现了长度不小于 \lfloor\frac d2\rfloor 的 s 的子串当且仅当行走的路径上经过了深度大于等于 \lfloor\frac d2\rfloor 的点。

接下来是数字范围的限制，套路地差分一下转化为 [1,y] 的答案减掉 [1,x-1] 的答案，然后这种数字上界的限制自然想到数位 dp。

记 dp_{i,0/1,0/1,j} 表示填了前 i 位，当前前缀是否顶上界，是否已经经过了深度大于 \lfloor\frac d2\rfloor 的点，当前位于 AC 自动机上 j 号点的方案数。

转移的时候直接枚举下一位填什么，沿着 AC 自动机上的边走过去即可。

时间复杂度 O(n^2d)，可以滚动数组优化掉第一维状态。

#include<iostream>
#include<cstdio>
#include<queue>
#include<string>
#include<cstring>
using namespace std;
const int mod=1000000007;
int n,m,tot,ch[500001][11],fail[500001],dep[500001],dp[2][2][2][500001],now;
string s,a,b;
inline int Mod(int x)
{
    return x>=mod? x-mod:x;
}
inline void insert(int x)
{
    int node=0;
    for(int i=x;i<=n;++i)
    {
        if(!ch[node][s[i]-'0'])
        {
            ch[node][s[i]-'0']=++tot;
            dep[tot]=dep[node]+1;
        }
        node=ch[node][s[i]-'0'];
    }
}
inline void getfail()
{
    queue<int> q;
    for(int i=0;i<10;++i)
        if(ch[0][i])
            q.emplace(ch[0][i]);
    while(!q.empty())
    {
        int k=q.front();
        q.pop();
        for(int i=0;i<10;++i)
            if(ch[k][i])
            {
                fail[ch[k][i]]=ch[fail[k]][i];
                q.emplace(ch[k][i]);
            }
            else
                ch[k][i]=ch[fail[k]][i];
    }
}
inline int solve(string str)
{
    memset(dp,0,sizeof dp);
    now=0;
    dp[0][1][0][0]=1;
    for(int i=1;i<=m;++i)
    {
        int lim=str[i]-'0';
        now^=1;
        memset(dp[now],0,sizeof dp[now]);
        for(int j=0;j<2;++j)
            for(int k=0;k<2;++k)
                for(int p=0;p<=tot;++p)
                    if(dp[now^1][j][k][p])
                        for(int g=0;g<=(j? lim:9);++g)
                            dp[now][j&&g==lim][k||dep[ch[p][g]]>=(m>>1)][ch[p][g]]=Mod(dp[now][j&&g==lim][k||dep[ch[p][g]]>=(m>>1)][ch[p][g]]+dp[now^1][j][k][p]);
    }
    int res=0;
    for(int i=0;i<2;++i)
        for(int j=0;j<=tot;++j)
            res=Mod(res+dp[now][i][1][j]);
    return res;
}
int main()
{
    cin>>s>>a>>b;
    n=s.length();
    m=a.length();
    s=" "+s;
    a=" "+a;
    b=" "+b;
    --a[m];
    for(int i=m;i>=1&a[i]<'0';--i)
    {
        a[i]='9';
        --a[i-1];
    }
    for(int i=1;i<=n;++i)
        insert(i);
    getfail();
    cout<<Mod(solve(b)-solve(a)+mod)<<'\n';
    return 0;
}