BCD code 题解 -> 传送门
AC当然可以，由于数据非常小，可以使用更暴力的字符串\(dp\)方法，本质相同
注意到所有的数位\(dp\) , 都是从首位开始加数字的 , 那么在每一次加入过后 , 若这段后缀字符串已经与某个字符串相同 , 这个状态一定不会继续
而它的后缀与某一字符串相同的条件 , 一定是与某个字符串的某一段前缀相同!
所以 , 我们定义某一个字符串的状态为它是那段字符串的哪一个前缀 , 而其他的状态实际并没有意义
string s[N];
vector <string> S;
S.clear();S.push_back("");
for(int i=1; i<=n; i++){
string t;t.clear();
for(int j=0,len=s[i].size(); j<len; j++){
t.push_back(s[i][j]);
S.push_back(t);
}
}
sort(S.begin(),S.end());
S.erase(unique(S.begin(),S.end()),S.end());
int k=S.size();
这里我们用一个\(vector\)存下了所有状态
(当然是要\(unique\)去重的)
也就是说 , 现在我们给每个字符串定义了一个状态(以及一个\(0\)匹配的字符串状态)
接下来考虑状态的转移
在这道题中 , 我们每次实际只会在字符串的末尾加入一个\(0/1\)
而这段字符加入后必然产生一个新的状态 , 即找到一段新的前缀与它的后缀匹配
那如何匹配呢?(算法请滚开)
不断删去第一个字符 , 然后找找有没有匹配即可
都排好序了 , 匹配当然用\(lowerbound()\)啦
for(int i=0;i<k;i++){
c[i]=0;
for(int j=1;j<=n;j++){
if(s[j].size()<=S[i].size()){
if(s[j]==S[i].substr(S[i].size()-s[j].size(),S[i].size())){
c[i]=1;
break;
}
}
}
for(int j=0;j<2;j++){
string tmp=S[i]+char(j^'0');
while(1){
int p=lower_bound(S.begin(),S.end(),tmp)-S.begin();
if(p<k)if(S[p]==tmp){ Nxt[i][j]=p; break; }
tmp=tmp.substr(1);
}
}
}
预处理复杂度\(O(n^2 \cdot 20^2 +n \cdot log(n) \cdot 20)\) 以及很大的常数
这里我们善用了C++优秀的\(string\)操作
然后我们预处理好了\(Nxt[i][j]\)即在第\(i\)个状态后加入\(j\)达到的新状态
如果想让算法再快点 , 还可以把加入每个数字的结果预处理出来
for(int i=0;i<k;i++){
for(int j=0;j<10;j++){
C[i][j]=c[i];
int now=i;
for(int o=3; o>=0; o--)
now=Nxt[now][(j&(1<<o))>0],C[i][j]|=c[now];
nxt[i][j]=now;
}
}
注意这里的\(C[i][j]\)数组代表这个状态会不会与某一字符串匹配
那么预处理完再直接跑数位\(dp\)岂不是很棒
数位\(dp\) -> 传送门
还有初始状态一定是\(0\)匹配状态
整体\(Code\)
#include <cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
using namespace std;
const int N=210,MOD=1e9+9;
typedef long long ll;
int n,m,k;
string s[N];
vector <string> S;
bool c[N*10],C[N*10][100];
int Nxt[N][N],nxt[N][N];
void init(){
S.clear();S.push_back("");
for(int i=1; i<=n; i++){
string t;t.clear();
for(int j=0,len=s[i].size(); j<len; j++){
t.push_back(s[i][j]);
S.push_back(t);
}
}
sort(S.begin(),S.end()),S.erase(unique(S.begin(),S.end()),S.end());
k=S.size();
for(int i=0;i<k;i++){
c[i]=0;
for(int j=1;j<=n;j++){
if(s[j].size()<=S[i].size()){
if(s[j]==S[i].substr(S[i].size()-s[j].size(),S[i].size())){
c[i]=1;
break;
}
}
}
for(int j=0;j<2;j++){
string tmp=S[i]+char(j^'0');
while(1){
int p=lower_bound(S.begin(),S.end(),tmp)-S.begin();
if(p<k)if(S[p]==tmp){ Nxt[i][j]=p; break; }
tmp=tmp.substr(1);
}
}
}
for(int i=0;i<k;i++){
for(int j=0;j<10;j++){
C[i][j]=c[i];
int now=i;
for(int o=3; o>=0; o--)now=Nxt[now][(j&(1<<o))>0],C[i][j]|=c[now];
nxt[i][j]=now;
}
}
}
struct node{
int a[N],len;
void Get(){
char s[N];
memset(a,0,sizeof a);
scanf("%s",s);
len=strlen(s);
for(int i=0;i<len;i++)a[len-i]=s[i]^'0';
}
void Dec(void){
a[1]--;
int p=1;
while(a[p]<0&&p<=len)a[p]+=10,a[p+1]--,p++;
while(a[len]==0&&len>=1)len--;
len=max(len,1);
}
}X;
int f[N][N*10][4];
int dfs(int p,int limit,int k,bool fl){
if(!p)return fl;
if(!limit&&~f[p][k][fl])return f[p][k][fl];
int R=limit?X.a[p]:9,ans=0;
for(int i=0;i<=R;i++){
int nk=k,nfl=fl||i;
if(nfl){
nk=nxt[nk][i];
if(C[k][i])continue;
}
(ans+=dfs(p-1,limit&&i==R,nk,nfl))%=MOD;
}
if(!limit)f[p][k][fl]=ans;
return ans;
}
int Solve(){
m=X.len;
return dfs(m,1,0,0);
}
int L,R;
int main(){
int T;scanf("%d",&T);
for(int kase=1; kase<=T; kase++){
memset(f,-1,sizeof f);
scanf("%d",&n);
for(int i=1; i<=n; i++)cin>>s[i];
init();
X.Get();X.Dec();
int res=-Solve();
X.Get();
res+=Solve();
res=(res%MOD+MOD)%MOD;
printf("%d\n",res);
}
}