正題

題目鏈接:https://www.luogu.com.cn/problem/P3311

---

題目大意

求一個不超過$n$的數(shù)字使其不包含任何$s$集合中的數(shù)字串。

---

解題思路

很經(jīng)典的$AC$自動機上面$dp$，但是因為是數(shù)字所以要來點數(shù)位$dp$的東西，多開一維用$0/1$表示是否在上界，然后每次要加入一些新的值以確保沒有前導$0$。

時間復雜度$O(n{\sum }_{i=1}^m|s_i|)$

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #include<queue> using namespace std; const int N=2100,P=1e9+7; int m,cnt,siz[N],fail[N],ch[N][10],f[2][N][2]; char n[N],s[N];queue<int> q; void Insert(char *s){int l=strlen(s),x=0;for(int i=0;i<l;i++){int c=s[i]-'0';if(!ch[x][c])ch[x][c]=++cnt;x=ch[x][c];}siz[x]++; } void Get_Fail(){for(int i=0;i<10;i++)if(ch[0][i])q.push(ch[0][i]);while(!q.empty()){int x=q.front();q.pop();for(int i=0;i<10;i++){if(!ch[x][i])ch[x][i]=ch[fail[x]][i];else{fail[ch[x][i]]=ch[fail[x]][i];q.push(ch[x][i]);}}}return; } int main() {scanf("%s",n+1);int l=strlen(n+1);scanf("%d",&m);for(int i=1;i<=m;i++){scanf("%s",s);Insert(s);}Get_Fail();int ans=0;for(int i=1;i<=l;i++){memset(f[i&1],0,sizeof(f[i&1]));int lim=n[i]-'0';if(i==1){for(int k=1;k<lim;k++)(f[i&1][ch[0][k]][0]+=1)%=P;(f[i&1][ch[0][lim]][1]+=1)%=P;}elsefor(int k=1;k<10;k++)(f[i&1][ch[0][k]][0]+=1)%=P;for(int j=0;j<=cnt;j++){if(siz[j])continue;for(int k=0;k<10;k++)(f[i&1][ch[j][k]][0]+=f[~i&1][j][0])%=P;for(int k=0;k<lim;k++)(f[i&1][ch[j][k]][0]+=f[~i&1][j][1])%=P;(f[i&1][ch[j][lim]][1]+=f[~i&1][j][1])%=P;}}for(int i=0;i<=cnt;i++)if(!siz[i])(ans+=(f[l&1][i][0]+f[l&1][i][1])%P)%=P;printf("%d\n",ans); } 創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結(jié)

以上是生活随笔為你收集整理的P3311-[SDOI2014]数数【AC自动机,dp】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。