题目
n<=50，代表字母表里最多n个字母，
然后p个被禁止的串，
问串长不超过m有多少合法串
思路来源
https://www.cnblogs.com/kuangbin/p/3159954.html
题解
其实和前面的几道题基本一样，
就是需要用大数，然后调调参就过了
矩阵快速幂可以用dp替代，
dp[i][j]代表串长不超过i的以状态j结尾的方案数，
由于必须从根节点root=状态0出发，
所以预处理dp[0][0]=1,dp[0][其他]=0，
在AC自动机上走m条边，即再走m个节点即可
然后由于大数空间比较吃紧，
开个滚动数组优化一下
注意更新dp[i][j]之前先给清零，
不然里面是dp[i-2][j]的值
心得
哎又是一题debug1h系列，凉凉
以后串长还是开大一点吧
gets字符串s[]，本来估的上限55，结果re了
然后开到65才过的……
其实大可不必这么抠空间……
开个几百也没啥问题……
但的确想知道为什么略高于理论上界不行，很迷啊
kuangbin老师的大数板子不错，回头整理一下QAQ
自己的都需要init，不能直接大数和数加或乘，比较鸡肋
这么试下界的我也是非常菜了……
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
struct node
{
int fail,Next[55];
bool tag;
}trie[105];
char s[65];
int id[55],cnt;
int que[105];//建ac自动机的队列
int root,tot;//根的编号 节点编号
ull ans;
int n,m,p;
struct Matrix
{
ull a[110][110];
int r;
Matrix():r(105){
memset(a,0,sizeof a);
}
Matrix(int n):r(n)//考虑0次的单位矩阵
{
for(int i=0;i<n;++i)
{
for(int j=0;j<n;++j)
{
a[i][j]=0;
}
}
}
Matrix operator*(const Matrix &b)const
{
Matrix tmp(r);
for(int i=0;i<r;++i)
{
for(int j=0;j<r;++j)
{
for(int k=0;k<r;++k)
{
tmp.a[i][j]+=a[i][k]*b.a[k][j];
}
}
}
return tmp;
}
}M;
/*
Matrix p(1),q(2),N;
Matrix modpow(Matrix x,ll n)
{
Matrix p(x.r);
for(int i=0;i<p.r;++i)
p.a[i][i]=1;
while(n)
{
if(n&1)p=p*x;
x=x*x,n/=2;
}
return p;
}
Matrix S(Matrix a,ll k)
{
Matrix b(2*a.r);
for(int i=0;i<a.r;++i)
{
for(int j=0;j<a.r;++j)
{
b.a[i][j]=a.a[i][j];
}
b.a[a.r+i][i]=b.a[a.r+i][a.r+i]=1;
}
b=modpow(b,k+1);
return b;
}*/
void insert(int r,char *s)//(root,串),trie树插入
{
int len=strlen(s);
for(int i=0;i<len;i++)
{
if(trie[r].Next[id[s[i]]]==0)
{
trie[r].Next[id[s[i]]]=++tot;
trie[trie[r].Next[id[s[i]]]].tag=0;
}
r=trie[r].Next[id[s[i]]];
}
trie[r].tag=1;//是病毒的结尾
//if(trie[r].tag)printf("%d\n",r);
}
void build(int r,int N)//建ac自动机
{
int head=0,tail=0;
trie[r].fail=r;//root自己连自己
que[tail++]=r;
while(head<tail)
{
r=que[head++];
if(trie[trie[r].fail].tag)trie[r].tag=1;//后缀的最后一个字母是病毒 那么自己也是 importance1
for(int i=0;i<N;i++)
{
int ch=trie[r].Next[i],failp;
if(ch)
{
que[tail++]=ch;
for(failp=trie[r].fail;failp!=root&&trie[failp].Next[i]==0;failp=trie[failp].fail);//向前回跳
if(trie[failp].Next[i]==0||trie[failp].Next[i]==ch)trie[ch].fail=failp;//接到根或者自己
else trie[ch].fail=trie[failp].Next[i];//可以后接
}
else trie[r].Next[i]=trie[trie[r].fail].Next[i];//和fail续一个一模一样的后继 importance2
}
}
}
void debug()
{
for(int i=0;i<M.r;++i)
{
for(int j=0;j<M.r;++j)
printf("%llu ",M.a[i][j]);
puts("");
}
}
void buildMatrix(int N)
{
M=Matrix(tot);
for(int i=1;i<=tot;++i)
{
//if(trie[i].tag) printf("%d ",i);
for(int j=0;j<N;++j)
{
if(!trie[i].tag&&!trie[trie[i].Next[j]].tag)
M.a[i-1][max(trie[i].Next[j]-1,0)]++;
}
}
//debug();
}
struct BigInt
{
const static int mod=10000;
const static int LEN=4;
int a[800],len;
BigInt()
{
memset(a,0,sizeof(a));
len=1;
}
void init(int x)
{
memset(a,0,sizeof(a));
len=0;
do//四位一存 如123456789存为 6789 2345 1
{
a[len++]=x%mod;
x/=mod;
}while(x);
}
void Init(const char s[])//重点 123 4567
{
memset(a,0,sizeof(a));
int l=strlen(s),res=0;
len=l/LEN;
if(l%LEN)len++;//l/LEN向上取整 len=2 表明需要两个字节能存下
for(int i=l-1;i>=0;i-=LEN)
{
int t=0,k=max(i-LEN+1,0);//k是找到当前字节的最高位 回退len-1长 防越界
for(int j=k;j<=i;j++)t=t*10+s[j]-'0';//从4开始 t临时存储4567
a[res++]=t;//将低位存入
}
}
int Compare(const BigInt &b)//位多的大
{
if(len<b.len)return -1;
if(len>b.len)return 1;
for(int i=len-1;i>=0;i--)//从高位比较
if(a[i]<b.a[i])return -1;
else if(a[i]>b.a[i])return 1;
return 0;//完全相等的情况
}
BigInt operator +(const BigInt &b)const
{
BigInt ans;
ans.len=max(len,b.len);
for(int i=0;i<=ans.len;i++)ans.a[i]=0;
for(int i=0;i<ans.len;i++)
{
ans.a[i]+=((i<len)?a[i]:0)+((i<b.len)?b.a[i]:0);//防止越位现象
ans.a[i+1]+=ans.a[i]/mod;//向高位进位
ans.a[i]%=mod;
}
if(ans.a[ans.len]>0)ans.len++;//产生了9999+9999=9998 1的数组高位进位
return ans;
}
BigInt operator -(const BigInt &b)const//确保被减数大 差为正
{
BigInt ans;
ans.len=len;
int k=0;
for(int i=0;i<ans.len;i++)
{
ans.a[i]=a[i]+k-b.a[i];
if(ans.a[i]<0)ans.a[i]+=mod,k=-1;//向a[i]高位借10000,k=-1下轮生效
else k=0;
}
while(ans.a[ans.len-1]==0&&ans.len>1)ans.len--;//把前缀0去掉 如果ans.len=1时说明a=b差为0
return ans;
}
BigInt operator *(const BigInt &b)const
{
BigInt ans;
for(int i=0;i<len;i++)
{
int k=0;
for(int j=0;j<b.len;j++)
{
int temp=a[i]*b.a[j]+ans.a[i+j]+k;//模拟小学生乘法 i*j加到i+j上去 k为低位来的进位
ans.a[i+j]=temp%mod;
k=temp/mod;//k为向高位进的位 下一轮生效
}
if(k!=0)ans.a[i+b.len]=k;//高位进位 99*99=9801 右起第1位*右起第1位还是能到右起第3位的
}
ans.len=len+b.len;//4位数*4位数不会超过8位数
while(ans.a[ans.len-1]==0&&ans.len>1)ans.len--;//查出实际长度
return ans;
}
BigInt operator /(const int &n)const//被确保被除数大 商为正
{
BigInt ans;
ans.len=len;
int k=0;
for(int i=ans.len-1;i>=0;i--)
{
k=k*mod+a[i];//k=上一位来的退位*10000+这一位
ans.a[i]=k/n;//这一位除以n
k=k%n;//这一位除以n的余数送给下一位,i=0最后一位如57/28余的1直接丢掉 取整
}
while(ans.a[ans.len-1]==0&&ans.len>1)ans.len--;
return ans;
}
ll operator %(const int &n)const
{
ll ans=0;
for(int i=len-1;i>=0;i--)
{
ans=ans*mod+a[i];
if(ans>n)ans%=n;
}
return ans;
}
void output()
{
printf("%d",a[len-1]);//是多少就是多少 没有前缀0
for(int i=len-2;i>=0;i--)
printf("%04d",a[i]);//包含前缀0 如0001
printf("\n");
}
};
BigInt dp[2][111],tmp;
void init1()
{
trie[0].tag=0;//向虚节点转移
//p.a[0][0]=26;
}
void init2(int N)
{
memset(trie,0,sizeof trie);//只刷一个,之后插入的时候再刷
ans=tot=0;
root=++tot;
gets(s);
for(int i=0;i<N;++i)id[s[i]]=i;
}
int main()
{
init1();
while(~scanf("%d%d%d",&n,&m,&p))
{
gets(s);
init2(n);
for(int i=0;i<p;i++)
{
gets(s);
insert(root,s);
}
build(root,n);
buildMatrix(n);
//debug();puts("");
int now=0;
for(int i=1;i<tot;++i)dp[now][i].init(0);
dp[now][0].init(1);//初始状态由0结尾 代表只能从0开始转移
//dp[i][j]表示 串长不超过i的 以j结尾的状态
//类似后补1个的区间dp操作 初始化
//由串长不超过i-1的 以k结尾 状态k->状态j转移而来
for(int i=0;i<m;++i)//tot上限10*10
{
now^=1;
for(int j=0;j<tot;++j)//滚动数组的初始化
dp[now][j].init(0); //不然会受到i-2的答案的影响 重要
for(int j=0;j<tot;++j)
{
for(int k=0;k<tot;++k)
{
if(!M.a[j][k])continue;
tmp.init(M.a[j][k]);
dp[now][k]=dp[now][k]+dp[now^1][j]*tmp;
}
}
}
BigInt res;
for(int i=0;i<tot;++i)//以任意结尾均可 因为初始化的时候 不可的均赋0
res=res+dp[now][i];
res.output();
}
return 0;
}
版权声明：本文为Code92007原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。