首页 > 代码库 > BZOJ3530: [Sdoi2014]数数
BZOJ3530: [Sdoi2014]数数
3530: [Sdoi2014]数数
Time Limit: 10 Sec Memory Limit: 512 MBSubmit: 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
3
2
3
14
Sample Output
14
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位的就没有什么限制了，直接枚举每一位走就可以了。
代码：
1 #include<cstdio> 2 3 #include<cstdlib> 4 5 #include<cmath> 6 7 #include<cstring> 8 9 #include<algorithm> 10 11 #include<iostream> 12 13 #include<vector> 14 15 #include<map> 16 17 #include<set> 18 19 #include<queue> 20 21 #include<string> 22 23 #define inf 1000000000 24 25 #define maxn 2000+5 26 27 #define maxm 20000000+5 28 29 #define eps 1e-10 30 31 #define ll long long 32 33 #define pa pair<int,int> 34 35 #define for0(i,n) for(int i=0;i<=(n);i++) 36 37 #define for1(i,n) for(int i=1;i<=(n);i++) 38 39 #define for2(i,x,y) for(int i=(x);i<=(y);i++) 40 41 #define for3(i,x,y) for(int i=(x);i>=(y);i--) 42 43 #define mod 1000000007 44 45 using namespace std; 46 47 inline int read() 48 49 { 50 51 int x=0,f=1;char ch=getchar(); 52 53 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 54 55 while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();} 56 57 return x*f; 58 59 } 60 int n,m,cnt,a[maxn],go[maxn],t[maxn][26],f[maxn][maxn][2]; 61 char s[maxn]; 62 bool v[maxn]; 63 queue<int>q; 64 inline void add() 65 { 66 scanf("%s",s+1);int len=strlen(s+1),now=1; 67 for1(i,len) 68 { 69 int x=s[i]-‘0‘; 70 if(!t[now][x])t[now][x]=++cnt; 71 now=t[now][x]; 72 } 73 v[now]=1; 74 } 75 void bfs() 76 { 77 q.push(1); 78 while(!q.empty()) 79 { 80 int x=q.front(),y,j;v[x]|=v[go[x]];q.pop(); 81 for0(i,9) 82 { 83 j=go[x]; 84 while(j&&!t[j][i])j=go[j]; 85 if(t[x][i]) 86 { 87 go[y=t[x][i]]=j?t[j][i]:1; 88 q.push(y); 89 }else t[x][i]=j?t[j][i]:1; 90 } 91 } 92 } 93 94 int main() 95 96 { 97 98 freopen("input.txt","r",stdin); 99 100 freopen("output.txt","w",stdout);101 scanf("%s",s+1);n=strlen(s+1);102 for1(i,n)a[i]=s[i]-‘0‘;103 104 m=read();cnt=1;105 for0(i,9)t[1][i]=++cnt;106 while(m--)add();107 bfs();108 for1(i,a[1])if(!v[t[1][i]])f[1][t[1][i]][i==a[1]]=1;109 for1(i,n-1)110 for1(j,cnt)111 {112 for0(k,a[i+1])if(!v[t[j][k]])(f[i+1][t[j][k]][k==a[i+1]]+=f[i][j][1])%=mod;113 for0(k,9)if(!v[t[j][k]])(f[i+1][t[j][k]][0]+=f[i][j][0])%=mod;114 }115 int ans=0;116 for1(i,cnt)(ans+=f[n][i][0])%=mod,(ans+=f[n][i][1])%=mod;117 memset(f,0,sizeof(f));118 for1(i,9)if(!v[t[1][i]])f[1][t[1][i]][0]=1;119 for1(i,n-2)120 for1(j,cnt)121 for0(k,9)122 if(!v[t[j][k]])(f[i+1][t[j][k]][0]+=f[i][j][0])%=mod;123 for1(i,n-1)124 for1(j,cnt)125 (ans+=f[i][j][0])%=mod;126 printf("%d\n",ans);127 128 return 0;129 130 }
BZOJ3530: [Sdoi2014]数数
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。