P3311 [SDOI2014]数数 题解


以下题解仅供学习参考使用。

抄袭、复制题解,以达到刷AC率/AC数量或其他目的的行为,在洛谷是严格禁止的。

洛谷非常重视学术诚信。此类行为将会导致您成为作弊者。具体细则请查看洛谷社区规则

评论

  • 千年之狐_天才
    hack! 100 1 001
  • 千年之狐_天才
    hack错误,当我没说
  • command_block
    Hack! 100 3 01 02 03
  • command_block
    暴力删边不可取……
作者: ButterflyDew 更新时间: 2019-02-21 11:04  在Ta的博客查看 举报    5  

看大家好像都写的挺麻烦的?

关于多子串的东西可以想到AC自动机,可以在上面dp。

$dp_{i,j,0/1}$代表$i\sim n$位数字目前在AC自动机上匹配到节点$j$是否有最高位限制。

最后一位可以像数位dp那样非常简单的转移。

然后有个坑点是$S$中有前导$0$,但是$N$中没有。

有一种简单的处理方法是在建完AC自动机后把边$ch[root][0]$删掉


Code:

#include <cstdio>
#include <cstring>
const int mod=1e9+7;
const int N=1520;
inline void add(int &x,int y){x=x+y>=mod?x+y-mod:x+y;}
char s[N],t[N];
int ch[N][10],endro[N],fail[N],tot,q[N],l=1,r,bit[N],dp[N][N][2];
void ins()
{
    scanf("%s",s+1);
    int n=strlen(s+1),now=0;
    for(int i=1;i<=n;i++)
    {
        if(!ch[now][s[i]-'0']) ch[now][s[i]-'0']=++tot;
        now=ch[now][s[i]-'0'];
    }
    endro[now]=1;
}
void build()
{
    for(int i=0;i<10;i++)
        if(ch[0][i])
            q[++r]=ch[0][i];
    while(l<=r)
    {
        int now=q[l++];
        for(int i=0;i<10;i++)
        {
            if(ch[now][i]) fail[q[++r]=ch[now][i]]=ch[fail[now]][i];
            else ch[now][i]=ch[fail[now]][i];
        }
    }
    ch[0][0]=0;
}
int main()
{
    scanf("%s",t+1);
    int n=strlen(t+1),m;
    for(int i=1;i<=n;i++) bit[i]=t[n+1-i]-'0';
    scanf("%d",&m);
    for(int i=1;i<=m;i++) ins();
    build();
    dp[n+1][0][1]=1;
    for(int i=n+1;i>1;i--)
        for(int j=0;j<=tot;j++)
            for(int l=0;l<=1;l++)
                for(int k=0,u=l?bit[i-1]:9;k<=u;k++)
                {
                    int to=ch[j][k];
                    if(!endro[to]) add(dp[i-1][to][l&k==bit[i-1]],dp[i][j][l]);
                }
    int ans=mod-1;
    for(int i=0;i<=tot;i++) add(ans,dp[1][i][0]),add(ans,dp[1][i][1]);
    printf("%d\n",ans);
    return 0;
}

评论

  • _zzy
    奇怪的变量名....
  • HNYLMS_MuQiuFeng
    dp方程前面两点是不是应该从0开始枚举啊?就是那个ch(p,1~9)和ch(p,1~upper_i - 1)
作者: Ebola 更新时间: 2018-10-23 17:13  在Ta的博客查看 举报    5  

对给定的若干个串建立AC自动机。对自动机上的每个节点,维护一个标记,表示在fail树上,它到根的路径中是否存在词尾节点。(词尾节点即每次插入一个串时最后到达的那个节点)

设$f_{i,j,0/1}$表示考虑到n的第i位(从高到低),当前在自动机的j号节点,目前为止 没有挨着 / 正在挨着 上界时,答案是多少。设ch(x,c)表示x号节点的c号子节点,于是可以写出转移:

  1. 若当前没有挨着上界,前一位不挨着上界,则:$f_{i-1,p,0}\longrightarrow f_{i,ch(p,1\sim 9),0}$
  2. 若当前没有挨着上界,前一位挨着上界,则:$f_{i-1,p,1}\longrightarrow f_{i,ch(p,1\sim upper_i-1),0}$
  3. 若当前要挨着上界,那前一位必然要挨着上界,则 :$f_{i-1,p,1}\longrightarrow f_{i,ch(p,upper_i),1}$

最后的答案显然就是:$\sum\limits_{i=0}^{tot}f_{n,i,0}+f_{n,i,1}$

经过尝试,使用滚动数组会大大提升运行速度,可以快20ms左右!

#include<bits/stdc++.h>
using namespace std;

const int N=1510;
const int ha=1000000007;
int ch[N][10],fail[N],tot=0;
int f[2][N][2],m,nlen;
bool fuck[N];
char n[N];

void insert(char* _begin,char* _end)
{
    int o=0;
    for(;_begin!=_end;_begin++)
    {
        int t=*_begin-'0';
        if(!ch[o][t]) ch[o][t]=++tot;
        o=ch[o][t];
    }
    fuck[o]=1;
}

void getfail()
{
    queue<int> q;q.push(0);
    while(!q.empty())
    {
        int u=q.front();q.pop();
        fuck[u]|=fuck[fail[u]];
        for(int i=0;i<10;i++)
            if(ch[u][i])
            {
                if(u) fail[ch[u][i]]=ch[fail[u]][i];
                q.push(ch[u][i]);
            }
            else ch[u][i]=ch[fail[u]][i];
    }
}

inline void add(int &x,const int &y){x=(x+y>=ha)?x+y-ha:x+y;}

int xixihaha()
{
    int ans=0,k=0;
    for(int i=1;i<n[0]-'0';i++)
        add(f[k][ch[0][i]][0],1);
    add(f[k][ch[0][n[0]-'0']][1],1);
    for(int i=1;i<nlen;i++,k^=1)
    {
        memset(f[k^1],0,sizeof(f[k^1]));
        for(int j=1;j<10;j++)
            add(f[k^1][ch[0][j]][0],1);
        for(int p=0;p<=tot;p++)
        {
            if(fuck[p]) continue;
            if(f[k][p][0])for(int j=0;j<10;j++)
            {
                if(fuck[ch[p][j]]) continue;
                add(f[k^1][ch[p][j]][0],f[k][p][0]);
            }
            if(f[k][p][1])for(int j=0;j<n[i]-'0';j++)
            {
                if(fuck[ch[p][j]]) continue;
                add(f[k^1][ch[p][j]][0],f[k][p][1]);
            }
            if(fuck[ch[p][n[i]-'0']]) continue;
            add(f[k^1][ch[p][n[i]-'0']][1],f[k][p][1]);
        }
    }
    for(int i=0;i<=tot;i++)
    {
        if(fuck[i]) continue;
        add(ans,f[k][i][0]);
        add(ans,f[k][i][1]);
    }
    return ans;
}

int main()
{
    char s[N];
    scanf("%s%d",n,&m);
    nlen=strlen(n);
    for(int i=0;i<m;i++)
    {
        scanf("%s",s);
        int len=strlen(s);
        insert(s,s+len);
    }
    getfail();
    int ans=xixihaha();
    printf("%d\n",ans);
    return 0;
}

评论

  • 还没有评论
作者: ωαηg 更新时间: 2019-05-04 08:29  在Ta的博客查看 举报    1  

看到题解里面都是递推式dp,我来补一发记忆化搜索式的


主要思路

楼上已经讲得很清楚了。但为了过审为了加深理解,我还是来略讲一下。

看到题目里的多模式串匹配,显然可以想到AC自动机。再看到“计算不大于N的幸运数个数”,我们又可以发现这与数位dp有关。所以这题的算法正是:AC自动机+数位dp。

首先是AC自动机的基本操作,把集合S读进来,建立trie树,求出前缀指针。

然后,我们的问题就转化为了:在加上前缀指针的trie树上,找一条路径,不经过任何结尾节点,并且一路上经过的边所组成的数字不大于$n$,有多少种方案。

数位dp实现。

注意,一个节点是结尾节点,当且仅当这个点本身是结尾节点,或者其失配节点是结尾节点,或者其失配节点的失配节点是结尾节点,或者其失配节点的失配节点的。。。是结尾节点。我么可以用AC自动机求完前缀指针之后队列里面的残留数据来实现这一点。(具体见代码)


代码实现

AC自动机基本操作不再多讲,不会请自行补习。

这里重点讲一下数位dp。

我们设$f[i][j]$表示当前在处理第i位,当前在trie树的j这个节点,并且保证当前构成的数严格小于n,接下去有多少个符合要求的数字。

显然,在转移的时候,我们可以暴力枚举接下来选哪一个数。假设接下去选的数是k:

$f[i][j]=\sum f[i+1][ch[j][k]](ch[j][k]$ 不是结尾节点$)$

我们可以用记忆化搜索实现这一转移,代码如下:(我的数位dp中大小限制变量与别人是反过来的,阅读可能引起不适,请谅解):

int dfs(int pos,int ch_pos,bool down,bool qiandaoling){
    if(pos>lenn) return !qiandaoling;//注意,请处理前导零问题
    if(down && ~f[pos][ch_pos]) return f[pos][ch_pos];//~f[pos][ch_pos]是f[pos][ch_pos]!=-1的装逼写法
    int end=down?9:sn[pos]-'0',res=0;//阅读可能引起不适,请谅解。
    for(int i=0;i<=end;i++){
        if(qiandaoling){//处理前导零问题
            if(!bo[ch[1][i]])
              res=(res+dfs(pos+1,ch[1][i],down || i!=end,qiandaoling && i==0))%p;//转移
        }
        else{
            if(!bo[ch[ch_pos][i]])
              res=(res+dfs(pos+1,ch[ch_pos][i],down || i!=end,false))%p;//转移
        }
    }
    if(down && !qiandaoling) f[pos][ch_pos]=res;//记忆化
    return res;
}

可以看到,我们刚刚处理了前导零问题。那么为什么要处理前导零呢?因为此题数据太坑爹。

我们可以看看这个数据:

10

1

01

如果你不处理前导零,那么你的输出将是9,而正确输出则是10.

因为在数位dp的时,我们在构成数字1的过程中一不小心包含了“01”这个子串(因为我们的n有两位,所以是从十位开始数位dp的)。而事实上,数字1是不包含"01"这个子串的,因为那个0是前导零。

所以我们要特判一下,忽略前导零。


真 · 代码

#include<bits/stdc++.h>
#define int long long
#define next fuck
using namespace std;
int const max_ch=1505;
int const p=1e9+7;
int m,lenn,tot=1,ch[max_ch][10],next[max_ch],que[max_ch],f[1205][max_ch];
bool bo[max_ch];
char sn[1205],s[1505];
inline void insert(char *s){
    int u=1,len=strlen(s);
    for(int i=0;i<len;i++){
        int c=s[i]-'0';
        if(!ch[u][c]) ch[u][c]=++tot;
        u=ch[u][c];
    }
    bo[u]=true;
}
inline void get_next(){
    for(int i=0;i<10;i++)
      ch[0][i]=1;
    next[1]=0,que[1]=1;
    for(int l=1,r=1;l<=r;l++){
        int u=que[l];
        for(int i=0;i<10;i++){
            if(!ch[u][i]) ch[u][i]=ch[next[u]][i];
            else{
                que[++r]=ch[u][i];
                next[ch[u][i]]=ch[next[u]][i];
            }
        }
    }
}
int dfs(int pos,int ch_pos,bool down,bool qiandaoling){
    if(pos>lenn) return !qiandaoling;
    if(down && ~f[pos][ch_pos]) return f[pos][ch_pos];
    int end=down?9:sn[pos]-'0',res=0;
    for(int i=0;i<=end;i++){
        if(qiandaoling){
            if(!bo[ch[1][i]])
              res=(res+dfs(pos+1,ch[1][i],down || i!=end,qiandaoling && i==0))%p;
        }
        else{
            if(!bo[ch[ch_pos][i]])
              res=(res+dfs(pos+1,ch[ch_pos][i],down || i!=end,false))%p;
        }
    }
    if(down && !qiandaoling) f[pos][ch_pos]=res;
    return res;
}
signed main(){
    scanf("%s",sn+1);
    lenn=strlen(sn+1);
    scanf("%lld",&m);
    for(int i=1;i<=m;i++){
        scanf("%s",s);
        insert(s);
    }
    get_next();
    for(int i=1;i<=tot;i++)
      bo[que[i]]=bo[que[i]] || bo[next[que[i]]];
    //利用队列里的残留数据
    memset(f,-1,sizeof(f));
    printf("%lld\n",dfs(1,1,false,true));
    return 0;
}

评论

  • 还没有评论
作者: wzj423 更新时间: 2018-07-17 15:30  在Ta的博客查看 举报    1  

看到这道题,很容易想到以下AC自动机上的dp方程:

/**
    f[0][i][j]表示该位不受限制,AC自动机节点为i,匹配到了第j位的方案数
    f[1][i][j]表示该位受限制,AC自动机节点为i,匹配到了第j位的方案数
    f[2][i][j]表示该位以及之前都是前导零, 

    因而有:
    for(int nx=0;nx<10;++nx)
        f[0][i][j]->f[0][c[i][nx]][j+1]

    for(int nx=0;nx<N[j];++nx)
        f[1][i][j]->f[0][c[i][nx]][j+1]
    f[1][i][j]->f[1][c[i][nx nx==N[j] ][j+1]

*/

但这样只能得到80分,会Wa两个点 这是为什么?我们可以看一看数据:

0821463255
0383320100380
001153611528
066512243919
0321614037728
0835268196243

(4.in)

这时835268196243XXXXX在AC自动机上的路径为0-8-3-5... 这本来是一组可行解,但因为错误地考虑了前导零而排除了 因而我们需要重新设计方程:

/**
    f[0][i][j]表示该位不受限制,AC自动机节点为i,匹配到了第j位的方案数
    f[1][i][j]表示该位受限制,AC自动机节点为i,匹配到了第j位的方案数
    f[2][i][j]表示该位以及之前都是前导零, AC自动机节点为i,匹配到了第j位的方案数
    则有转移:
    for(int nx=0;nx<10;++nx)
        f[0][i][j]->f[0][c[i][nx]][j+1]

    for(int nx=0;nx<N[j];++nx)
        f[1][i][j]->f[0][c[i][nx]][j+1]
    f[1][i][j]->f[1][c[i][nx nx==N[j] ][j+1]

    f[1][0][0]->f[2][0][1] nx==0
    f[1][0][0]->f[0][c[0][nx]][1] nx!=0

    f[2][0][j]->f[2][0][j+1] nx==0
    f[2][0][j]->f[0][c[0][i][j+1]
*/

这样就能AC了

80pts Ver:

#include <bits/stdc++.h>
/*80*/
using namespace std;
//defs==============================
const int mod=1e9+7,MAXP=1700,MAXN=1300;
int M;
char N[MAXN],p[MAXN];int Nlen;
long long ans;
bool tot0;
//AC==========================================
int c[MAXP][10],val[MAXP],fail[MAXP],cnt,_rt=0;
bool is_tot0(char *s) {
    int len=strlen(s);
    for(int i=0;i<len;++i) if(s[i]!='0')    return false;
    return true;
}
void ins(char *s) {
    int len=strlen(s),now=_rt;
    for(int i=0;i<len;++i) {
        int v=s[i]-'0';
        if(!c[now][v])  c[now][v]=++cnt;
        now=c[now][v];
    }
    ++val[now];
}
void build_fail() {
    queue<int> q;
    for(int i=0;i<10;++i)   if(c[0][i]) q.push(c[0][i]);
    while(!q.empty()) {
        int u=q.front();q.pop();
        for(int i=0;i<10;++i)
            if(c[u][i]) fail[c[u][i]]=c[fail[u]][i],val[c[u][i]]+=val[fail[c[u][i]]],q.push(c[u][i]);
            else    c[u][i]=c[fail[u]][i];
    }
}
//dp======================
int f[2][MAXP][MAXN];
/*
    f[0][i][j]表示该位不受限制,AC自动机节点为i,匹配到了第j位的方案数
    f[1][i][j]表示该位受限制,AC自动机节点为i,匹配到了第j位的方案数
    f[2][i][j]表示该位以及之前都是前导零, 
    for(int nx=0;nx<10;++nx)
        f[0][i][j]->f[0][c[i][nx]][j+1]

    for(int nx=0;nx<N[j];++nx)
        f[1][i][j]->f[0][c[i][nx]][j+1]
    f[1][i][j]->f[1][c[i][nx nx==N[j] ][j+1]

    f[1][0][0]->f[2][0][1] nx==0
    f[1][0][0]->f[0][c[0][nx]][1] nx!=0

    f[2][0][j]->f[2][0][j+1] nx==0
    f[2][0][j]->f[0][c[0][i][j+1]

*/
int vis[2][MAXP][MAXN];
void pp(int i,int j,int k) {
//  printf("f[%d][%d][%d]=%d\n",i,j,k,f[i][j][k]);
}
//main================================= 
int main() {
    scanf("%s",N+1);Nlen=strlen(N+1);
    scanf("%d",&M);
    for(int i=1;i<=M;++i) scanf("%s",p),ins(p),tot0|=is_tot0(p);
    build_fail();
    //for(int i=0;i<=cnt;++i)
    //  printf("id=%d 0=%d 1=%d 2=%d 3=%d 4=%d val=%d fail=%d\n",i,c[i][0],c[i][1],c[i][2],c[i][3],c[i][4],val[i],fail[i]);
    vis[1][0][0]=f[1][0][0]=1;
    for(int j=0;j<Nlen;++j){
        for(int i=0;i<=cnt;++i) {
            for(int limit=0;limit<=1;++limit) {
                if(!vis[limit][i][j])   continue;
            //  printf("from (%d,%d,%d)\n",limit,i,j);
                if(limit==0) {
                    //puts("limit=0");
                    for(int nx=0;nx<10;++nx)
                        if(!val[c[i][nx]])
                            (f[0][c[i][nx]][j+1]+=f[0][i][j])%=mod,vis[0][c[i][nx]][j+1]=true,pp(0,c[i][nx],j+1);
                } else {
                    //puts("limit=1");
                    for(int nx=0;nx<N[j+1]-'0';++nx)
                        if( /*!(j==0&&nx==0) &&*/ !val[c[i][nx]])
                            (f[0][c[i][nx]][j+1]+=f[1][i][j])%=mod,vis[0][c[i][nx]][j+1]=true,pp(0,c[i][nx],j+1);
                    if(!val[c[i][ N[j+1]-'0' ]]) {
                        (f[1][c[i][ N[j+1]-'0' ]][j+1]+=f[1][i][j])%=mod;
                        vis[1][ c[i][ N[j+1]-'0' ] ][j+1]=true;
                        //puts("special");
                        pp(1,c[i][N[j+1]-'0'],j+1);                     
                    }

                }
            }
        }
    }
    for(int i=0;i<=cnt;++i) {
        (ans+=f[0][i][Nlen])%=mod;
        (ans+=f[1][i][Nlen])%=mod;
    }
    if(tot0)
        printf("%lld\n",ans);
    else
        printf("%lld\n",ans-1);
    return 0;
}

100pts Ver

#include <bits/stdc++.h>
using namespace std;
//defs==============================
const int mod=1e9+7,MAXP=1700,MAXN=1300;
int M;
char N[MAXN],p[MAXN];int Nlen;
long long ans;
bool tot0;
//AC==========================================
int c[MAXP][10],val[MAXP],fail[MAXP],cnt,_rt=0;
bool is_tot0(char *s) {
    int len=strlen(s);
    for(int i=0;i<len;++i) if(s[i]!='0')    return false;
    return true;
}
void ins(char *s) {
    int len=strlen(s),now=_rt;
    for(int i=0;i<len;++i) {
        int v=s[i]-'0';
        if(!c[now][v])  c[now][v]=++cnt;
        now=c[now][v];
    }
    ++val[now];
}
void build_fail() {
    queue<int> q;
    for(int i=0;i<10;++i)   if(c[0][i]) q.push(c[0][i]);
    while(!q.empty()) {
        int u=q.front();q.pop();
        for(int i=0;i<10;++i)
            if(c[u][i]) fail[c[u][i]]=c[fail[u]][i],val[c[u][i]]+=val[fail[c[u][i]]],q.push(c[u][i]);
            else    c[u][i]=c[fail[u]][i];
    }
}
//dp======================
int f[3][MAXP][MAXN];
/*
    f[0][i][j]表示该位不受限制,AC自动机节点为i,匹配到了第j位的方案数
    f[1][i][j]表示该位受限制,AC自动机节点为i,匹配到了第j位的方案数
    f[2][i][j]表示该位以及之前都是前导零, 
    for(int nx=0;nx<10;++nx)
        f[0][i][j]->f[0][c[i][nx]][j+1]

    for(int nx=0;nx<N[j];++nx)
        f[1][i][j]->f[0][c[i][nx]][j+1]
    f[1][i][j]->f[1][c[i][nx nx==N[j] ][j+1]

    f[1][0][0]->f[2][0][1] nx==0
    f[1][0][0]->f[0][c[0][nx]][1] nx!=0

    f[2][0][j]->f[2][0][j+1] nx==0
    f[2][0][j]->f[0][c[0][i]][j+1] nx!=0

*/
int vis[3][MAXP][MAXN];
void pp(int i,int j,int k) {
    //printf("f[%d][%d][%d]=%d\n",i,j,k,f[i][j][k]);
}
inline void add(int &a,int b) {
    (a+=b)%=mod;
}
//main================================= 
int main() {
    scanf("%s",N+1);Nlen=strlen(N+1);
    scanf("%d",&M);
    for(int i=1;i<=M;++i) scanf("%s",p),ins(p),tot0|=is_tot0(p);
    build_fail();
    //for(int i=0;i<=cnt;++i)
    //  printf("id=%d 0=%d 1=%d 2=%d 3=%d 4=%d val=%d fail=%d\n",i,c[i][0],c[i][1],c[i][2],c[i][3],c[i][4],val[i],fail[i]);
    vis[1][0][0]=f[1][0][0]=1;
    for(int j=0;j<Nlen;++j){
        for(int i=0;i<=cnt;++i) {
            for(int limit=0;limit<=2;++limit) {
                if(!vis[limit][i][j])   continue;
                if(limit==0) {
                    for(int nx=0;nx<10;++nx)
                        if(!val[c[i][nx]])
                            add(f[0][c[i][nx]][j+1],f[0][i][j]),vis[0][c[i][nx]][j+1]=true,pp(0,c[i][nx],j+1);
                } else if(limit==1){
                    for(int nx=(j==0);nx<N[j+1]-'0';++nx)
                        if(!val[c[i][nx]]) {
                            add(f[0][c[i][nx]][j+1],f[1][i][j]);
                            vis[0][c[i][nx]][j+1]=true;
                            pp(0,c[i][nx],j+1);                             
                        }
                    if(j==0){
                        add(f[2][0][1],f[1][0][0]); 
                        vis[2][0][1]=true;
                        pp(2,0,1);
                    }
                    if(!val[c[i][ N[j+1]-'0' ]]) {
                        add(f[1][  c[i][ N[j+1]-'0'  ]][j+1],f[1][i][j]);
                        vis[1][ c[i][ N[j+1]-'0' ] ][j+1]=true;
                        pp(1,c[i][N[j+1]-'0'],j+1);                     
                    }                       
                } else if(limit==2) {
                    add(f[2][0][j+1],f[2][0][j]);
                    vis[2][0][j+1]=1;
                    pp(2,0,j+1);
                    for(int nx=1;nx<10;++nx)
                        if(!val[c[i][nx]]) {
                            add(f[0][c[i][nx]][j+1],f[2][0][j]);
                            vis[0][c[i][nx]][j+1]=true;
                            pp(0,c[i][nx],j+1);                             
                        }
                }
            }
        }
    }
    for(int i=0;i<=cnt;++i) {
        (ans+=f[0][i][Nlen])%=mod;
        (ans+=f[1][i][Nlen])%=mod;
    }
    printf("%lld\n",ans);
    return 0;
}

评论

  • 还没有评论
作者: 暴躁的蒟蒻 更新时间: 2017-07-14 14:32  在Ta的博客查看 举报    1  

AC自动机 + DP

【解题思路】

参考http://blog.csdn.net/Regina8023/article/details/44974979

先用 $AC$ 自动机对 $S$ 集合的字符串建立 $Trie$ 树,记数组 $nxt$ 表示 $AC$ 自动机的失败指针,数组 $lst[x]$ 在点 $x$ 表示沿着失败指针能否走到一个 $S$ 集合中的串末尾,如有则记为这个字符串的编号。

然后我们记 $f[i][j][k]$ 表示当前已经确定到第 $i$ 位数,走到 $AC$ 自动机上的节点 $j$,且状态为 $k$ 的总方案数(因为要处理前导0的问题,这里的第 $i$ 位从高位向低位计算,当取最高位,即 $i = 1$ 时,应不包含取0的方案数)。

对于状态 $k$,我们有如下定义:

[1]. $k = 0$ 已经确定的 $i$ 位数小于 $N$ 的前 $i$位;

[2]. $k = 1$ 已经确定的 $i$ 位数等于 $N$ 的前 $i$ 位;

[3]. $k = 2$ 已经确定的 $i$ 位数大于 $N$ 的前 $i$ 位。

接下来我们考虑如何转移:枚举第 $i + 1$ 位选取的数字 $num$,可以利用我们刚才的 $AC$ 自动机判断:这样确定的 $i + 1$ 位数字是否存在某个 $S$ 集合中的串是它的后缀。如不存在我们就可以确定 $AC$ 自动机上的节点 $x$,则 $f[i + 1][x][k’]$ 就可以由 $f[i][j][k]$ 转移过来,最终的转移如下(可结合此时已经确定的 $i$ 位数与 $N$ 的前 $i$ 位的大小关系来理解):

[1]. 若 $num$ 小于 $N$ 的第 $i + 1$ 位:

$f[i + 1][x][0] += f[i][j][0] + f[i][j][1]$

$f[i + 1][x][2] += f[i][j][2]$

[2]. 若 $num$ 等于 $N$ 的第 $i + 1$ 位:

$f[i + 1][x][0] += f[i][j][0] $

$f[i + 1][x][1] += f[i][j][1]$

$f[i + 1][x][2] += f[i][j][2]$

[3]. 若 $num$ 大于 $N$ 的第 $i + 1$位:

$f[i + 1][x][0] += f[i][j][0]$

$f[i + 1][x][2] += f[i][j][2] + f[i][j][1]$

每确定一位数都要将 $\sum \limits^2_{k’ = 0} f[i + 1][j][k’]$ 累加进答案 $Ans$,同时因为幸运数不能大于 $N$,所以最终的答案还要减去 $\sum f[n][j][2]$($n$ 为数 $N$ 的位数)。

【代码】

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long ll;
const int Maxn = 0x3f3f3f3f;
const int N = 1505, M = 1205;
const ll Mod = 1e9 + 7;
ll f[M][N][3], Ans; 
bool pos[N]; char s[M], a[N]; 
int n, m, T, G[N][10], Q[N], nxt[N], lst[N];
inline int get()
{
    char ch; bool f = false; int res = 0;
    while (((ch = getchar()) < '0' || ch > '9') && ch != '-');
    if (ch == '-') f = true;
     else res = ch - '0';
    while ((ch = getchar()) >='0' && ch <= '9')
        res = (res << 3) + (res << 1) + ch - '0';
    return f? ~res + 1 : res;
}
inline void put(int x)
{
    if (x < 0)
      x = ~x + 1, putchar('-');
    if (x > 9) put(x / 10);
    putchar(x % 10 + 48);
}
inline void Insert()
{
    scanf("%s", a + 1); 
    int x = 0, l = strlen(a + 1);
    for (int i = 1; i <= l; ++i)
    {
        int y = a[i] - '0';
        if (!G[x][y]) G[x][y] = ++T;
        x = G[x][y]; 
    }
    pos[x] = true;
}
inline void Bfs()
{
    int t, w, x, y; t = w = 0; 
    for (int i = 0; i < 10; ++i)
     if (G[0][i]) Q[++w] = G[0][i];
    while (t < w)
    {
        x = Q[++t];
        for (int i = 0; i < 10; ++i)
         if (!G[x][i]) G[x][i] = G[nxt[x]][i];
         else 
         {
             Q[++w] = y = G[x][i]; int v = nxt[x];
            while (!G[v][i] && v) v = nxt[v];
            nxt[y] = G[v][i];
            lst[y] = pos[nxt[y]] ? nxt[y] : lst[nxt[y]]; 
         }
    }
}
inline int cmp(const int &x, const int &y)
{
    if (x > y) return 2;
    if (x < y) return 0;
    return 1; 
}
int main()
{
    scanf("%s", s + 1); 
    n = strlen(s + 1); m = get();
    while (m--) Insert(); Bfs();
    for (int i = 1; i < 10; ++i) //不含前导0 
    {
        int x = G[0][i];
        if (!pos[x] && !lst[x]) f[1][x][cmp(i, s[1] - '0')]++;
    }
    for (int i = 0; i <= T; ++i)
     (Ans += f[1][i][0] + f[1][i][1] + f[1][i][2]) %= Mod;
    for (int i = 1; i < n; ++i)
    {
        for (int j = 0; j <= T; ++j)
        if (f[i][j][0] || f[i][j][1] || f[i][j][2])
        for (int k = 0; k < 10; ++k)
        {
            int x = j;
            while (!G[x][k] && x) x = nxt[x];
            x = G[x][k]; 
            if (pos[x] || lst[x]) continue;
            int v = cmp(k, s[i + 1] - '0');
            switch (v)
            {
                case 0:
                  (f[i + 1][x][0] += f[i][j][0] + f[i][j][1]) %= Mod;
                  (f[i + 1][x][2] += f[i][j][2]) %= Mod; break;
                case 1:
                  (f[i + 1][x][0] += f[i][j][0]) %= Mod;
                  (f[i + 1][x][1] += f[i][j][1]) %= Mod;
                  (f[i + 1][x][2] += f[i][j][2]) %= Mod; break;
                case 2:    
                  (f[i + 1][x][2] += f[i][j][2] + f[i][j][1]) %= Mod;
                  (f[i + 1][x][0] += f[i][j][0]) %= Mod; break;
            }
         }
         for (int j = 0; j <= T; ++j)
         {
             (Ans += f[i + 1][j][0] + f[i + 1][j][1]) %= Mod;
             if (i + 1 < n) (Ans += f[i + 1][j][2]) %= Mod;
        }
    }
    return put(Ans), 0;
}
 
反馈
如果你认为某个题解有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。