WA记录

相关思路我都写在代码前的注释里面了

在这里也放一下代码：

/*
basic[i] 表示第 i 个基本词汇
ban[i] 表示第 i 个禁忌词汇

给 ban[] 建 Trie 图
nxtN[u][i] 表示在 Trie 图上 u 节点，跑一段 basic[i] 之后到哪个节点（相当于有一个若干长度的串，在 Trie 图上跑完在 u 节点，然后在
这个串后面接一个 basic[i] ，再跑一次会到哪里）
如果跑的过程中路过了代表某个 ban 的节点，那就把 nxtN[u][i] 置为 -1 ，表示这个转移行不通 
f[u][L] 表示当前串的长度为 L ，在 Trie 图上跑一遍到了 u 节点，有多少种方案
初始：f[0][0] = 1 
转移：对于 u,i,L
有 f[nxtN[u][i]][L+len(basic[i])]+=f[u][L] (nxtN[u][i]!=-1) 
Ans : 
\sum_{u 不是代表某个 ban 的节点}{f[u][L]}

预计算 nxtN[][] : O(10000N) 

暴力转移 O(100NL) 60pts 
point 7,8 : 每次 L 只会变化 1 ，矩阵快速幂
point 9,10 : 每次 L 最多变化 2 ，把两列 f[][] 合在一起用矩阵快速幂  
 
shaber 分讨题 /fn 
原理上，我应该可以把最多 100 列的 f[][] 合在一起用矩阵快速幂，实际上我也确实可以这么干，复杂度看起来像是 O(100^3 * (\log L) ) 的  
先这样，我先写 60 分暴力，看看 dp 对不对
然后写分讨写法，以后有空再写一个统一的解法 

需要注意的是：point 9,10 的 "合在一起" 指的是把两列并成一列，然后做）
那如果这样的话，就不太能把 100 列并在一起了 ? 

现在暴力挂了一个点，point9,10 都挂了 
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int N=55;
const int SZ=105;
const int B=26;
const int MAXL=105;
int nBasic,nBan;
string basic[N],ban[N];
int L;
int nxtN[SZ][N];
int lenBasic[N];  //基本单词长度 
ll f[SZ][MAXL*2];

int ch[SZ][B],fail[SZ],nNode=0,rt=0;  //Trie 图 
bool endt[SZ];  //endt[u] 表示 Trie 图上 u 节点是否代表某个禁忌单词 

void insert(string str){
	int cur=rt;
	for(int i=0;i<str.size();i++){
		int nxt=str[i]-'a';
		if(!ch[cur][nxt])ch[cur][nxt]=++nNode;
		cur=ch[cur][nxt];
	}
	endt[cur]=1;
}

void buildACM(){
	queue<int> q;
	for(int i=0;i<B;i++)if(ch[rt][i])q.push(ch[rt][i]),fail[ch[rt][i]]=rt;
	while(!q.empty()){
		int cur=q.front();  q.pop();
		for(int i=0;i<B;i++){
			if(ch[cur][i])q.push(ch[cur][i]),fail[ch[cur][i]]=ch[fail[cur]][i];
			else ch[cur][i]=ch[fail[cur]][i];
		}
	}
}

void getNextNode(){
	memset(nxtN,-1,sizeof(nxtN)); 
	for(int u=0,cur;u<=nNode;u++)if(!endt[u]){
		for(int i=1;i<=nBasic;i++){
			cur=u;
			for(int j=0;j<lenBasic[i];j++){
				cur=ch[cur][basic[i][j]-'a'];
				if(endt[cur]){
					nxtN[u][i]=-1;cur=-1;break;
				}
			}
			nxtN[u][i]=cur;
		}
	} 
}

namespace subtask1{
	void solve(){
		f[0][0]=1;
		for(int l=0;l<=L;l++)
			for(int u=0;u<=nNode;u++)
				for(int i=1;i<=nBasic;i++)if(nxtN[u][i]!=-1){
					f[nxtN[u][i]][l+lenBasic[i]]=(f[nxtN[u][i]][l+lenBasic[i]]+f[u][l])%mod;
				}
		ll ans=0;
		for(int u=0;u<=nNode;u++)if(!endt[u])ans=(ans+f[u][L])%mod;
		cout<<ans<<endl;
	}
}

struct Matrix{
	int r,c;
	ll dat[SZ*2][SZ*2];
	Matrix (int _r=0,int _c=0){r=_r,c=_c,memset(dat,0,sizeof(dat));}
	Matrix operator*(Matrix b){
		Matrix a=*this;
		Matrix ret(a.r,b.c);
		for(int i=1;i<=a.r;i++)
			for(int j=1;j<=b.c;j++)
				for(int k=1;k<=a.c;k++){
					ret.dat[i][j]=(ret.dat[i][j]+a.dat[i][k]*b.dat[k][j]%mod)%mod;
				}
		return ret;
	}
	Matrix operator^(ll y){
		Matrix x=*this,ret=*this;
		y--;
		while(y){
			if(y&1)ret=ret*x;
			x=x*x;
			y>>=1;
		}
		return ret;
	}
};

namespace subtask2{
	void solve(){
		Matrix F(nNode+1,1),trans(nNode+1,nNode+1);
		F.dat[1][1]=1;
		for(int u=0;u<=nNode;u++)
			for(int i=1;i<=nBasic;i++)
				if(nxtN[u][i]!=-1){
					trans.dat[nxtN[u][i]+1][u+1]++;
				}
//		cout<<"trans: \n";
//		for(int i=1;i<=nNode+1;i++,cout<<endl)
//			for(int j=1;j<=nNode+1;j++)cout<<trans.dat[i][j]<<" ";cout<<endl;
//		cout<<"nxtN: \n";
//		for(int u=0;u<=nNode;u++,cout<<endl)
//			for(int i=1;i<=nBasic;i++)cout<<nxtN[u][i]<<" ";cout<<endl;
		
		F=(trans^L)*F;
		
//		trans=trans^L;
//		cout<<"trans^L: \n";
//		for(int i=1;i<=nNode+1;i++,cout<<endl)
//			for(int j=1;j<=nNode+1;j++)cout<<trans.dat[i][j]<<" ";cout<<endl;
//		cout<<"F: \n";
//		for(int i=1;i<=nNode+1;i++)cout<<F.dat[i][1]<<endl;
		
		ll ans=0;
		for(int u=0;u<=nNode;u++)if(!endt[u])ans=(ans+F.dat[u+1][1])%mod;
		cout<<ans<<endl;
	}
}

namespace subtask3{
	void solve(){
		Matrix F(2*(nNode+1),1),trans(2*(nNode+1),2*(nNode+1));
		F.dat[1][1]=1;
		for(int i=1;i<=nBasic;i++){
			if(nxtN[rt][i]!=-1&&lenBasic[i]==1)F.dat[nNode+1+nxtN[rt][i]+1][1]=1;
			for(int u=0;u<=nNode;u++){
				if(lenBasic[i]==1){
					if(nxtN[u][i]!=-1){
//						trans.dat[nxtN[u][i]+1][u+1]++;
						trans.dat[nxtN[u][i]+1+nNode+1][u+1+nNode+1]++;
					}
				}
				else if(lenBasic[i]==2){
					if(nxtN[u][i]!=-1)trans.dat[nxtN[u][i]+1+nNode+1][u+1]++;
				}
			}
		}
		for(int i=0;i<=nNode;i++)
			for(int j=0;j<=nNode;j++)trans.dat[i+1][j+1+nNode+1]=1;
			
		F=(trans^L)*F;
		ll ans=0;
		for(int u=0;u<=nNode;u++)if(!endt[u])ans=(ans+F.dat[u+1][1])%mod;
		cout<<ans<<endl;
	}
}
/*
hack 
3 1 4
a
b
ab
aba
Ans=19
output=35
*/

int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	
	cin>>nBasic>>nBan>>L;
	
	for(int i=1;i<=nBasic;i++)cin>>basic[i],lenBasic[i]=basic[i].size();
	for(int i=1;i<=nBan;i++)cin>>ban[i],insert(ban[i]);
	
	buildACM();
	getNextNode();
	
	if(L<=100)
		subtask1::solve();
	else if(*max_element(lenBasic+1,lenBasic+1+nBasic)<=1)
		subtask2::solve();
	else
		subtask3::solve();
	
	return 0;
}

正如注释所说的，现在我在 L<=100里面挂了一个点，比较希望大家帮我看看这里有什么问题