程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> bzoj3530【SDOI2014】數數

bzoj3530【SDOI2014】數數

編輯:關於C++

 

3530: [Sdoi2014]數數

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

14

HINT

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


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

Source

Round 1 day 1

AC自動機+動態規劃,思路很棒

首先在Trie樹中加入失配邊,形成一個新的圖。

然後分兩種情況進行動態規劃,分別為位數小於l和等於l。當位數小於l時,沒有什麼限制,直接轉移就可以了;當位數等於l時,需要多加一維表示前i位的數是否等於n的前i位。(具體轉移詳見代碼)

另外這道題還有一點需要注意:因為幸運數是沒有前導零的,所以在圖中第一步不能走t[1][0]。

#include
#include
#include
#include
#include
#include
#include
#define F(i,j,n) for(int i=j;i<=n;i++)
#define D(i,j,n) for(int i=j;i>=n;i--)
#define ll long long
#define pa pair
#define maxn 1510
#define mod 1000000007
using namespace std;
int t[maxn][10],go[maxn],f[1210][maxn][2],a[maxn];
int tot=1,n,l,ans=0;
char s[maxn];
bool v[maxn];
queue q;
inline void insert()
{
	scanf("%s",s);
	int len=strlen(s),now=1;
	F(i,0,len-1)
	{
		int x=s[i]-'0';
		if (!t[now][x]) t[now][x]=++tot;
		now=t[now][x];
	}
	v[now]=1;
}
inline void bfs()
{
	q.push(1);
	while (!q.empty())
	{
		int x=q.front(),y,j;q.pop();v[x]|=v[go[x]];
		F(i,0,9)
		{
			j=go[x];
			while (j&&!t[j][i]) j=go[j];
			if (t[x][i])
			{
				go[y=t[x][i]]=j?t[j][i]:1;
				q.push(y);
			}
			else t[x][i]=j?t[j][i]:1;
		}
	}
}
int main()
{
	scanf("%s",s);
	l=strlen(s);
	F(i,0,l-1) a[i]=s[i]-'0';
	scanf("%d",&n);
	F(i,1,n) insert();
	bfs();
	memset(f,0,sizeof(f));
	F(i,1,9) if (!v[t[1][i]]) f[1][t[1][i]][0]+=1;
	F(i,1,l-2) F(j,1,tot) F(x,0,9) if (!v[t[j][x]])
		(f[i+1][t[j][x]][0]+=f[i][j][0])%=mod;
	F(i,1,l-1) F(j,1,tot) (ans+=f[i][j][0])%=mod;
	memset(f,0,sizeof(f));
	F(i,1,a[0]) if (!v[t[1][i]]) f[1][t[1][i]][i==a[0]]+=1;
	F(i,1,l-1) F(j,1,tot) F(x,0,9) if (!v[t[j][x]])
	{
		(f[i+1][t[j][x]][0]+=f[i][j][0])%=mod;
		if (x

 

 
  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved