题目链接: http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3494
题目大意：给定一些被禁止的BCD码。问指定范围内不含有任何这些禁止的BCD码的数的个数。
解题思路：
AC自动机部分：
首先insert这些被禁止的BCD码。
然后打一下自动机前后状态的转移的表，用BCD[i][j]表示自动机状态i时，下一个数字是j的自动机的下一个状态。
一开始我考虑最先dfs的位在自动机的位置，后来发现SB了。AC自动机有一个root状态，也就是自动机位置为0的状态，使用这个0就行了。
即f函数中dfs(len,0,true,true)，每次由root状态出发，无须再考虑其它的。
数位DP部分：
本题的范围是高精度范围，所以需要特有的高精度写法。
麻烦的在于f(l-1)，要为高精度手艹一个-1，有种偷懒的写法，不过会导致出现前导0。
所以在传统的dfs中需要增加一个前导0的判断。
方法是：追加一个bool z，
在原有的0~9基础上，单独考虑0，
if(z) 则单独dfs前导0
否则dfs正常的0，1~9照常dfs。当然还需要判断当前状态s的下一个状态BCD[s][i]是否符合要求。
然后最后就是注意一下负数mod。
#include "cstdio"
#include "cstring"
#include "queue"
#include "iostream"
using namespace std;
#define maxp 25*105
#define mod 1000000009
struct Trie
{
Trie *next[],*fail;
int cnt;
}pool[maxp],*root,*sz;
int BCD[maxp][],digit[],ccnt;
long long dp[][maxp];
Trie *newnode()
{
Trie *ret=sz++;
memset(ret->next,,sizeof(ret->next));
ret->fail=;
ret->cnt=;
return ret;
}
void init()
{
sz=pool;
root=newnode();
}
void Insert(string str)
{
Trie *pos=root;
for(int i=;i<str.size();i++)
{
int c=str[i]-'';
if(!pos->next[c]) pos->next[c]=newnode();
pos=pos->next[c];
}
pos->cnt++;
}
void getfail()
{
queue<Trie *> Q;
for(int c=;c<;c++)
{
if(root->next[c])
{
root->next[c]->fail=root;
Q.push(root->next[c]);
}
else root->next[c]=root;
}
while(!Q.empty())
{
Trie *x=Q.front();Q.pop();
for(int c=;c<;c++)
{
if(x->next[c])
{
x->next[c]->fail=x->fail->next[c];
x->next[c]->cnt+=x->fail->next[c]->cnt;
Q.push(x->next[c]);
}
else x->next[c]=x->fail->next[c];
}
}
}
int judge(int status,int num)
{
Trie *pos=pool+status;
if(pos->cnt) return -;
for(int i=;i>=;i--)
{
if(pos->next[(num>>i)&]->cnt) return -;
else pos=pos->next[(num>>i)&];
}
return pos-pool;
}
void getbcd()
{
for(int i=;i<ccnt;i++)
for(int j=;j<;j++)
BCD[i][j]=judge(i,j);
}
int dfs(int len,int s,bool fp,bool z)
{
if(!len) return ;
if(!fp&&dp[len][s]!=-) return dp[len][s];
long long ret=;
int fpmax=fp?digit[len]:;
if(z)
{
ret+=dfs(len-,s,fp&&digit[len]==,true);
ret%=mod;
}
else
{
if(BCD[s][]!=-) ret+=dfs(len-,BCD[s][],fp&&digit[len]==,false);
ret%=mod;
}
for(int i=;i<=fpmax;i++)
{
if(BCD[s][i]!=-) ret+=dfs(len-,BCD[s][i],fp&&i==fpmax,false);
ret%=mod;
}
if(!fp&&!z) dp[len][s]=ret;
return ret;
}
int f(string str)
{
int len=;
for(int i=str.size()-;i>=;i--)
digit[++len]=str[i]-'';
return dfs(len,,true,true);
}
int main()
{
//freopen("in.txt","r",stdin);
ios::sync_with_stdio(false);
int T,n;
string tt;
cin>>T;
while(T--)
{
init();
memset(dp,-,sizeof(dp));
cin>>n;
for(int i=;i<=n;i++)
{
cin>>tt;
Insert(tt);
}
getfail();
ccnt=sz-pool;
getbcd();
cin>>tt;
for(int i=tt.size()-;i>=;i--)
{
if(tt[i]>'') {tt[i]--;break;}
else {tt[i]='';}
}
long long ans=;
ans-=f(tt);
ans%=mod;
cin>>tt;
ans+=f(tt);
ans=(ans%mod+mod)%mod;
printf("%lld\n",ans);
}
}
| 2842327 | neopenx | ZOJ 3494 | Accepted | 4656 KB | 210 ms | C++ (g++ 4.4.5) | 2976 B | 2014-10-13 17:06:35 |