连环画
问题描述
连环画是一种特殊类型的填字游戏。
小马和小亮最近迷上了这个游戏。他们一共有n个不同的单词，每个单词有无限个。
他们很好奇如果各自拿若干个单词拼接成一个长为m的单词，有多少种方法能够使得两人拼接的单词相同。
他们可能不太聪明，所以请聪明的你来解决这个问题。
（如果对于任意两种方法，这两种方法中小马或小亮拿的单词不一样，则被认为是不同的。）
由于这个数字可能相当大，所以输出它的模数998244353。
输入
第一行包含两个整数n和m（1≤n≤8，1≤m≤10^9）-- 他们拥有的不同的单词数和需要拼接成的单词的长度。
接下来的n行中的每一行都包含一个词--一个不超过5个小写拉丁字母的非空字符串。所有的词都是保证不同。
输出
打印一个整数--给定的不同实例的数量对998244353取模。
输入例子 1 输出例子 1
3 5 ababa 11
ab a
输入例子 2 输出例子 2
2 4 ab 4
cd
输入例子 3 输出例子 3
5 100 a aa aaa 142528942
aaaa
aaaaa
提示
下面是对第一个例子的解释
字母上方的红线表示小马所拼接的单词，字母下方的蓝线表示小亮所拼接的单词。
先不考虑m的长度。
对于所有字母，我们可以考虑建出trie树。Trie上最多有40个节点。
然后设出dp[i][j][k]表示总共拼接出长为i，小马拼出的第i个字符为trie上的第j的节点，小亮拼出的为第k个节点
得出转移式dp[i][a][b]=sum（dp[i-1][c][d]）
特别的a,b分别为c,d的孩子，a所在trie上的字符等于b，c等于d。
我们还忽略掉了如何结束该单词，那么如果a点可以为一个单词的结尾，那么可以考虑转移到根节点上（根节点为1），即dp[i][1][b]=sum(dp[i-1][c][d])，同理b也要考虑。
但是m很大不能直接转移。
我们可以将dp后两维离散化成点，理论上有40*40个点，但是发现被转移的点条件比较苛刻，所以所有合法的状态不超过40*5个。
那么我们可以按照往年的惯例（bushi，对i这维矩阵快速幂。
通过dfs可以生成转移矩阵。
//by kexyfa
#include<bits/stdc++.h>
using namespace std;
const int P=998244353,N=170;
typedef array<array<int,N>,N> T; //定义矩阵
T w; //转移矩阵
int m,sz;
int f[N][26], //存储trie信息
g[N][N], //对于两人所在树上节点[a][b]关于矩阵的映射
ed[N];
T mul(T &a,T &b){
T c;
fill(&c[1][1],&c[m][m],0); //清空矩阵
for (int i=1;i<=m;++i)
for (int k=1;k<=m;++k)
for (int j=1;j<=m;++j)
c[i][j] = (1LL*a[i][k]*b[k][j] + c[i][j])%P;
return c;
}
int dfs(int a,int b){
auto &t=g[a][b];
if (t) return t;
t=g[b][a]=++m;
for (int i=0;i<26;++i){
int x=f[a][i],y=f[b][i];
if (x&&y){
w[t][dfs(x,y)]++; //直接转移
if (ed[x]) w[t][dfs(0,y)]++; //以x点为单词结尾
if (ed[y]) w[t][dfs(0,x)]++; //以y点为单词结尾
if (ed[x] &&ed[y]) w[t][dfs(0,0)]++; //两人一同结尾
}
}
return t;
}
void solve(){
int n,q;cin>>n>>q;
for (int i=0;i<n;++i){
string s;cin>>s;
int p=0;
for (char c:s){
auto&t=f[p][c-'a'];
if (!t) t=++sz;
p=t;
} //建立trie树
ed[p]=1; //标识有单词在p点结束
}
dfs(0,0); // 构造转移矩阵
T r;
fill(&r[1][1],&r[m][m],0);
r[1][1]=1;
for (;q;q>>=1,w=mul(w,w)) //矩阵快速幂
if (q&1) r=mul(r,w);
cout<<r[1][1];
}
int main(){
solve();
return 0-0;
}
标签：周赛,OJ,连环画,int,矩阵,单词,trie,拼接,dp From： https://www.cnblogs.com/hihopkc/p/16844466.html