BZOJ 3530 数数

发表于 | 更新于

Link

好题。 存在一处容易遗漏的细节： 若001∈S001 \in S，11合法。 出题人比较心软只卡了20pts。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
//Code by Lucida
#include<bits/stdc++.h>
#define get(x) scanf("%d",&x)
//#define debug(x) std::cout<<#x<<'='<<x<<std::endl
template <class T> inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
template <class T> inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}
const int MAXN=2000+10,P=1e9+7;
//正整数
namespace iAC
{
	const int SIZE=MAXN;
	const char SB='0',SE='9';
	const int SIGMA=SE-SB+1;
	struct Node
	{
		Node *son[SIGMA],*fail,*last;int cnt;
		int g[MAXN][2],f[MAXN];
		Node *&next(char c){return son[c-SB];}
		Node()
		{
			memset(son,0,sizeof(son));fail=last=0;cnt=0;
			memset(g,0,sizeof(g));memset(f,0,sizeof(f));
		}
	}*POOL=(Node*)malloc(SIZE*sizeof(Node)),*ME=POOL,*root=new(ME++) Node;
	Node *newNode(){return new(ME++) Node;}
	void Insert(char *s)
	{
		Node *cur=root;
		for(int i=1,L=strlen(s+1);i<=L;i++)
		{
			if(!cur->next(s[i])) cur->next(s[i])=newNode();
			cur=cur->next(s[i]);
		}
		cur->cnt++;
	}
	void Build()
	{
		static Node *Q[SIZE];int he=1,ta=0;
		root->fail=root;
		for(char c=SB;c<=SE;++c)
			if(!root->next(c)) root->next(c)=root;
			else
			{
				root->next(c)->fail=root;
				Q[++ta]=root->next(c);
			}
		while(he<=ta)
		{
			Node* cur=Q[he++];
			for(char c=SB;c<=SE;++c)
			{
				Node *&son=cur->next(c);
				if(!son) son=cur->fail->next(c);
				else
				{
					son->fail=cur->fail->next(c);
					son->last=son->fail->cnt?son->fail:son->fail->last;
					Q[++ta]=son;
				}
			}
		}
	}
}using namespace iAC;
typedef long long LL;
LL DP(char *N)
{
	LL res=0;int L=strlen(N+1);
	root->f[0]=1;
	for(int i=1;i<L;i++)
		for(Node *ptr=POOL;ptr!=ME;++ptr)
			for(char c=i==1?'1':'0';c<='9';++c)
				if(!ptr->next(c)->cnt && !ptr->next(c)->last)
					(ptr->next(c)->f[i]+=ptr->f[i-1])%=P;
	//res累加f[all][0~L-1]
	root->g[0][0]=1;
	for(int i=1;i<=L;i++)
		for(Node *ptr=POOL;ptr!=ME;++ptr)
			for(char c=i==1?'1':'0';c<='9';++c)
				if(!ptr->next(c)->cnt && !ptr->next(c)->last)
				{
					if(c==N[i])
						(ptr->next(c)->g[i][0]+=ptr->g[i-1][0])%=P;
					else if(c<N[i]) (ptr->next(c)->g[i][1]+=ptr->g[i-1][0])%=P;
					(ptr->next(c)->g[i][1]+=ptr->g[i-1][1])%=P;
				}

	for(Node *ptr=POOL;ptr!=ME;++ptr)
	{
		(res+=ptr->g[L][0]+ptr->g[L][1])%=P;
		for(int i=1;i<L;i++)
			(res+=ptr->f[i])%=P;
	}
	return res;
}
int main()
{
	static char N[MAXN],str[MAXN];
	scanf("%s",N+1);
	int m;get(m);
	for(int i=1;i<=m;i++)
	{
		scanf("%s",str+1);
		Insert(str);
	}
	Build();
	LL ANS=DP(N);
	printf("%lld\n",ANS);
	return 0;
}
/* AC Record(Bugs) *
 *	WA Naive.Detail ignored. 
 MLE LL Array MAXN to large
 NOT WA BUT next->last!!!
 * * * * * * * * * */