BZOJ3530: [Sdoi2014]数数

2022-09-17 22:51:26

3530: [Sdoi2014]数数

Time Limit: 10 Sec Memory Limit: 512 MB
Submit: 322 Solved: 188
[Submit][Status]

Description

我们称一个正整数N是幸运数，当且仅当它的十进制表示中不包含数字串集合S中任意一个元素作为其子串。例如当S=(22，333，0233)时，233是幸运数，2333、20233、3223不是幸运数。
给定N和S，计算不大于N的幸运数个数。

Input

输入的第一行包含整数N。
接下来一行一个整数M，表示S中元素的数量。
接下来M行，每行一个数字串，表示S中的一个元素。

Output

输出一行一个整数，表示答案模109+7的值。

Sample Input

20
3
2
3
14

Sample Output

HINT

下表中l表示N的长度，L表示S中所有串长度之和。

1 < =l < =1200 , 1 < =M < =100 ,1 < =L < =1500

题解：

orz居然自己做出来了。。。

定义f[i][j][k]表示到第i位，走到自动机上的j节点，k=0/1表示前面的数字是否都与N相同，也就是前面都是“贴”着过来的。

那么就很好转移了。这是数字满n位的情况。注意需要手动跑出第一位。

然后不满n位的就没有什么限制了，直接枚举每一位走就可以了。

代码：

 #include<cstdio>

 #include<cstdlib>

 #include<cmath>

 #include<cstring>

 #include<algorithm>

 #include<iostream>

 #include<vector>

 #include<map>

 #include<set>

 #include<queue>

 #include<string>

 #define inf 1000000000

 #define maxn 2000+5

 #define maxm 20000000+5

 #define eps 1e-10

 #define ll long long

 #define pa pair<int,int>

 #define for0(i,n) for(int i=0;i<=(n);i++)

 #define for1(i,n) for(int i=1;i<=(n);i++)

 #define for2(i,x,y) for(int i=(x);i<=(y);i++)

 #define for3(i,x,y) for(int i=(x);i>=(y);i--)

 #define mod 1000000007

 using namespace std;

 inline int read()

 {

     int x=,f=;char ch=getchar();

     while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

     while(ch>=''&&ch<=''){x=*x+ch-'';ch=getchar();}

     return x*f;

 }

 int n,m,cnt,a[maxn],go[maxn],t[maxn][],f[maxn][maxn][];

 char s[maxn];

 bool v[maxn];

 queue<int>q;

 inline void add()

 {

     scanf("%s",s+);int len=strlen(s+),now=;

     for1(i,len)

         {

             int x=s[i]-'';

             if(!t[now][x])t[now][x]=++cnt;

             now=t[now][x];

         }

     v[now]=;

 }

 void bfs()

 {

     q.push();

     while(!q.empty())

     {

         int x=q.front(),y,j;v[x]|=v[go[x]];q.pop();

         for0(i,)

         {

             j=go[x];

             while(j&&!t[j][i])j=go[j];

             if(t[x][i])

             {

                 go[y=t[x][i]]=j?t[j][i]:;

                 q.push(y);

             }else t[x][i]=j?t[j][i]:;

         }

     }

 }

 int main()

 {

     freopen("input.txt","r",stdin);

     freopen("output.txt","w",stdout);

     scanf("%s",s+);n=strlen(s+);

     for1(i,n)a[i]=s[i]-'';

     m=read();cnt=;

     for0(i,)t[][i]=++cnt;

     while(m--)add();

     bfs();

     for1(i,a[])if(!v[t[][i]])f[][t[][i]][i==a[]]=;

     for1(i,n-)

      for1(j,cnt)

       {

          for0(k,a[i+])if(!v[t[j][k]])(f[i+][t[j][k]][k==a[i+]]+=f[i][j][])%=mod;

          for0(k,)if(!v[t[j][k]])(f[i+][t[j][k]][]+=f[i][j][])%=mod;

       }

     int ans=;

     for1(i,cnt)(ans+=f[n][i][])%=mod,(ans+=f[n][i][])%=mod;

     memset(f,,sizeof(f));

     for1(i,)if(!v[t[][i]])f[][t[][i]][]=;

     for1(i,n-)

       for1(j,cnt)

         for0(k,)

          if(!v[t[j][k]])(f[i+][t[j][k]][]+=f[i][j][])%=mod;

     for1(i,n-)

       for1(j,cnt)

         (ans+=f[i][j][])%=mod;

     printf("%d\n",ans);

     return ;

 }

码农公寓