【BZOJ 3530】 [Sdoi2014]数数

3530: [Sdoi2014]数数

Time Limit: 10 Sec Memory Limit: 512 MB Submit: 422 Solved: 250 [Submit][Status][Discuss] 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

2032314

Sample Output

14

HINT

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

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

Source

Round 1 day 1

AC自动机上的dp。

做了【BZOJ 1030】，这道题就十分简单了。

对于集合S中所有的字符串，建一个AC自动机。

注意这个AC自动机要包含last，表示走到这个节点是否相当于走到了某个串的末尾（可能是这个串本身，，也可能是别的更短的串）

然后就可以dp了： 表示有的方案数。

状态: 位；

位；

位。

转移就是枚举下一位，判断是否可行。（详见代码）

;struct trie{int ch[12],mark,fail,last;}t[2005];char N[1500],s[1500];int m,tot=0,n[2000],l;LL f[1205][2005][3];void Insert(char s[]){int x=0;for (int i=0;i<strlen(s);i++){int c=s[i]-‘0’;if (!t[x].ch[c])t[x].ch[c]=++tot;x=t[x].ch[c];}t[x].mark=1;}void Make_fail(){queue<int> q;for (int i=0;i<=9;i++)if (t[0].ch[i])q.push(t[0].ch[i]);while (!q.empty()){int x=q.front();q.pop();for (int i=0;i<=9;i++)if (t[x].ch[i]){int y=t[x].ch[i];q.push(y);int v=t[x].fail;while (v&&!t[v].ch[i])v=t[v].fail;t[y].fail=v=t[v].ch[i];t[y].last=t[v].mark?v:t[v].last;}}}void Add(LL &a,LL b){a=(a+b)%mod;}int C(int a,int b){if (a==b) return 1;if (a<b) return 0;return 2;}void DP(){LL ans=0;for (int k=1;k<=9;k++){int v=t[0].ch[k];if (!t[v].mark&&!t[v].last)f[1][t[0].ch[k]][C(k,n[1])]+=1;}for (int j=0;j<=tot;j++)ans=(ans+f[1][j][0]+f[1][j][1]+f[1][j][2])%mod;for (int i=1;i<l;i++){for (int j=0;j<=tot;j++)if (f[i][j][0]||f[i][j][1]||f[i][j][2])for (int k=0;k<=9;k++){int v=j;while (v&&!t[v].ch[k])v=t[v].fail;v=t[v].ch[k];if (!t[v].mark&&!t[v].last){int x=C(k,n[i+1]);if (x==0)Add(f[i+1][v][0],f[i][j][0]+f[i][j][1]),Add(f[i+1][v][2],f[i][j][2]);if (x==1)Add(f[i+1][v][0],f[i][j][0]),Add(f[i+1][v][1],f[i][j][1]),Add(f[i+1][v][2],f[i][j][2]);if (x==2)Add(f[i+1][v][0],f[i][j][0]),Add(f[i+1][v][2],f[i][j][1]+f[i][j][2]);}}for (int j=0;j<=tot;j++){Add(ans,f[i+1][j][0]+f[i+1][j][1]);if (i+1!=l)Add(ans,f[i+1][j][2]);}}printf(“%d\n”,(int)ans%mod);}int main(){scanf(“%s”,N);l=strlen(N);for (int i=1;i<=l;i++)n[i]=N[i-1]-‘0’;scanf(“%d”,&m);for (int i=1;i<=m;i++)scanf(“%s”,s),Insert(s);Make_fail();DP();return 0;}

感悟： AC自动机上的dp用从的方式比较好转移。

心中有愿望一定要去闯，努力实现最初的梦想，