给定两张 (n_1/n_2) 个点 (m_1/m_2) 条边的有向图 (G_1,G_2)，每条边有一个小写字母。
定义字符串 (S) 和一条路径匹配当且仅当按顺序写下路径上边的字符，得到的字符串与 (S) 相同。
定义字符串 (S) 在一张图 (G) 的出现次数为 (G) 中与 (S) 匹配的路径数。
定义字符串 (S) 合法当且仅当 (S) 在 (G_1,G_2) 中的出现次数不相等。求最短的合法字符串 (S)，如果长度相同求字典序最小的，若不存在则判断无解。
(nle 500)，(mle 3000)。
题解说最短的合法串长度 (le n_1+n_2)。
考虑统计串 (s=s_1s_2cdots s_L) 在 (G_1,G_2) 中的出现次数之差：将两个图拼成 (n_1+n_2) 个点的大图 (G)，设 (f_{k,v}) 表示长度为 (k) 且与 (s_1cdots s_k) 匹配且最后一个节点是 (v) 的路径数量。
这是线性递推，可以写成矩阵形式：设 (26) 个字符的邻接矩阵是 (M_a,cdots,M_z)，(u_I^{ op}) 是元素均为 (1) 的行向量，(u_O) 是前 (n_1) 个元素为 (1)，后 (n_2) 个元素为 (-1) 的列向量，则串合法当且仅当 (u_I^{ op}M_{s_1}cdots M_{s_L}u_O e 0)。
设 (V_K) 表示所有 (Lle K) 的字符串 (s) 对应的行向量 (u_I^{ op}M_{s_1}M_{s_2}cdots M_{s_L}) 的集合，则最短的合法串长度 (le K) 当且仅当 (V_K) 中有元素 (u^{ op}) 满足 (u^{ op}u_O e 0)。
设 (U_K= ext{span}(V_K))，则又转化为 (U_K) 中有元素 (u^{ op}) 满足 (u^{ op}u_O e 0)。
对于行向量集合 (V) 和矩阵 (M)，设 (VM={u^{ op}M:uin V})，则
[V_K=V_{K-1}cupleft(igcup_{cinSigma}V_{K-1}M_c ight) \ U_K= ext{span}left(U_{K-1}cupleft(igcup_{cinSigma}U_{K-1}M_c ight) ight) ]显然 (U_1sube U_2subecdots)，且因为它是一阶递推式，而维数 (le n_1+n_2)，所以 (U_{n_1+n_2}=U_{n_1+n_2+1}=cdots)，所以若 (U_K) 内有元素 (u^{ op}u_O e 0)，则最小的 (Kle n_1+n_2)，得证。
结果发现上面这一长串并不重要（
重点在于不会 fst 的 Hash 技巧：生成 ((n_1+n_2)|Sigma|) 个随机数，表示每个位置的每个字符的 Hash 值，字符串的 Hash 值是其所有字符 Hash 值乘积，字符串集合的 Hash 值是其所有字符串 Hash 值之和。
先把长度求出来，最后按位贪心即可，时间复杂度 (O(nm|Sigma|))。
只要不卡就可以随便自然溢出...吗？既然是算乘积那肯定只能用奇数。
#include<bits/stdc++.h>
#define PB emplace_back
#define fi first
#define se second
using namespace std;
typedef pair<int, int> pii;
typedef unsigned long long u64;
const int N = 501;
template<typename T>
void rd(T &x){
int ch = getchar(); x = 0;
for(;ch < '0' || ch > '9';ch = getchar());
for(;ch >= '0' && ch <= '9';ch = getchar()) x = x * 10 + ch - '0';
}
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
u64 val[26][N<<1];
int L, cr;
struct Graph {
int n, le;
u64 f[N][N<<1], g[N], h[N];
vector<pii> E[N];
Graph(){
int m; rd(n); rd(m);
while(m --){
int u, v, c; rd(u); rd(v);
do c = getchar(); while(c < 'a' || c > 'z');
E[u].PB(v, c - 'a');
}
for(int i = 1;i <= n;++ i){
f[i][0] = g[i] = 1; h[i] = 0;
}
}
u64 work(){
u64 res = 0;
for(int i = 1;i <= n;++ i){
for(pii _ : E[i])
f[i][cr] += f[_.fi][cr-1] * val[_.se][cr];
res += f[i][cr];
} return res;
}
u64 calc(int c){
u64 res = 0;
for(int i = 1;i <= n;++ i)
for(pii _ : E[i]) if(_.se == c)
res += g[i] * val[c][cr-le] * f[_.fi][cr-le-1];
return res;
}
void upd(int c){
for(int i = 1;i <= n;++ i)
for(pii _ : E[i]) if(_.se == c)
h[_.fi] += g[i] * val[c][cr-le];
memcpy(g, h, n+1<<3);
memset(h, 0, n+1<<3); ++le;
}
} G1, G2;
int main(){
L = G1.n + G2.n;
for(int i = 0;i < 26;++ i)
for(int j = 1;j <= L;++ j)
val[i][j] = rng() | 1;
for(cr = 1;cr <= L;++ cr) if(G1.work() != G2.work()){
for(int i = 1;i <= cr;++ i)
for(int j = 0;j < 26;++ j) if(G1.calc(j) != G2.calc(j)){
putchar(j + 'a'); G1.upd(j); G2.upd(j); break;
}
return 0;
} puts("Same");
}