题意:求x-y之间有多少个数字包含至少k个密钥,密钥给出,x-y的数位比500小。
老年选手,这种题都不会做了,我退群吧。
就是随便AC自动机dp啊。。。我太废了。
设f[i][j][k][0/1]表示匹配到串的第i个节点,AC自动机上跑到了j,已经匹配了k个密钥,
0/1表示我之前匹配的哪些数位是否完全匹配某些密钥。
所以1可以转化为1或0,0只能转化0,然后xjbDP就好。。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
const int N=;
const int mo=+;
int n,k,cnt;
queue<int> q;
int ch[N][];
int val[N],f[N][N][][];
int fail[N];
char x[N],y[N],s[N];
inline void ins()
{
int len=strlen(s),x=;
fo(i,,len-)
{
char c=s[i]-'0';
if (ch[x][c])x=ch[x][c];
else x=ch[x][c]=++cnt;
}
val[x]++;
}
inline void getfail()
{
fo(i,,)
if(ch[][i])q.push(ch[][i]);
while (!q.empty())
{
int x=q.front();
q.pop();
fo(i,,)
if (!ch[x][i])ch[x][i]=ch[fail[x]][i];
else
{
q.push(ch[x][i]),
fail[ch[x][i]]=ch[fail[x]][i];
val[ch[x][i]]+=val[fail[ch[x][i]]];
}
}
}
inline int solve(char *a)
{
int len=strlen(a+);
memset(f,,sizeof(f));
f[][][][]=;
fo(i,,len-)
fo(j,,cnt)
fo(l,,k)
{
if (f[i][j][l][])
fo(c,,)
{
int tmp=min(k,l+val[ch[j][c]]);
(f[i+][ch[j][c]][tmp][]+=f[i][j][l][])%=mo;
}
if (f[i][j][l][])
{
int s1=a[i+]-'0';
int tmp=min(k,l+val[ch[j][s1]]);
(f[i+][ch[j][s1]][tmp][]+=f[i][j][l][])%=mo;
fo(c,,s1-)
{
tmp=min(k,l+val[ch[j][c]]);
(f[i+][ch[j][c]][tmp][]+=f[i][j][l][])%=mo;
}
}
}
int ans=;
fo(i,,cnt)(ans+=(f[len][i][k][]+f[len][i][k][])%mo)%=mo;
return ans;
}
int main()
{
freopen("word.in","r",stdin);
freopen("word.out","w",stdout);
scanf("%d%d%s%s",&n,&k,x+,y+);
fo(i,,n)
{
scanf("%s",s);
ins();
}
getfail();
printf("%d\n",(solve(y)-solve(x)+mo)%mo);
}