网站进度条特效,黑龙江建设网政务系统,修改wordpress上传文件大小,个人网站建设源代码「SDOI2014」数数 题目描述 我们称一个正整数 \(N\) 是幸运数#xff0c;当且仅当它的十进制表示中不包含数字串集合 \(S\) 中任意一个元素作为其子串。 例如当 \(S(\)22, 333, 0233\()\) 时#xff0c;233 是幸运数#xff0c;2333、20233、3223 不是幸运数。 给定 \(N\) 和…「SDOI2014」数数 题目描述 我们称一个正整数 \(N\) 是幸运数当且仅当它的十进制表示中不包含数字串集合 \(S\) 中任意一个元素作为其子串。 例如当 \(S(\)22, 333, 0233\()\) 时233 是幸运数2333、20233、3223 不是幸运数。 给定 \(N\) 和 \(S\)计算不大于 \(N\) 的幸运数个数。 输入格式 输入的第一行包含整数 \(N\)。 接下来一行一个整数 \(M\)表示 \(S\) 中元素的数量。 接下来 \(M\) 行每行一个数字串表示 \(S\) 中的一个元素。 输出格式 输出一行一个整数表示答案模 \(10^97\) 的值。 数据范围与提示 我们以 \(l\) 表示 \(N\) 的长度\(L\) 表示 \(S\) 中所有串长度之和。 对于所有数据\(1 \leq l \leq 1200 ,\ 1 \leq M \leq 100 ,\ 1 \leq L \leq 1500\)。 关于多子串的东西可以想到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 mod1e97;
const int N1520;
inline void add(int x,int y){xxymod?xy-mod:xy;}
char s[N],t[N];
int ch[N][10],endro[N],fail[N],tot,q[N],l1,r,bit[N],dp[N][N][2];
void ins()
{scanf(%s,s1);int nstrlen(s1),now0;for(int i1;in;i){if(!ch[now][s[i]-0]) ch[now][s[i]-0]tot;nowch[now][s[i]-0];}endro[now]1;
}
void build()
{for(int i0;i10;i)if(ch[0][i])q[r]ch[0][i];while(lr){int nowq[l];for(int i0;i10;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,t1);int nstrlen(t1),m;for(int i1;in;i) bit[i]t[n1-i]-0;scanf(%d,m);for(int i1;im;i) ins();build();dp[n1][0][1]1;for(int in1;i1;i--)for(int j0;jtot;j)for(int l0;l1;l)for(int k0,ul?bit[i-1]:9;ku;k){int toch[j][k];if(!endro[to]) add(dp[i-1][to][lkbit[i-1]],dp[i][j][l]);}int ansmod-1;for(int i0;itot;i) add(ans,dp[1][i][0]),add(ans,dp[1][i][1]);printf(%d\n,ans);return 0;
} 2019.2.21 转载于:https://www.cnblogs.com/butterflydew/p/10411119.html
