prologue
到底是谁查 UB 查了半天啊，原来是菜鱼啊。
analysis
这个题目我们不难推出来这个转移方程：
\[f_{i, j} \gets \sum_{k = 1} ^ {m} f_{i - 1, k} [k \in j \text{后面的合法集合}]
\]
我们看到 \(n\) 的值很大，而且上面的转移方程可以考虑写成一个矩阵乘法的形式。
我们构造一个答案矩阵 \(\begin{bmatrix}f_{i, 1} & f_{i, 2} & \cdots & f_{i, m}\end{bmatrix}\) 表示长度为 \(i\)
以题目中的样例一为例。
我们可以构造出来答案矩阵 \(\begin{bmatrix} f_{1} & f_{2} & f_{3}\end{bmatrix}\)
以及转移矩阵 \(\begin{bmatrix} 1 & 0 & 1 \\ 0 & 1 & 1 \\ 1 & 1 & 1 \end{bmatrix}\)
运用矩阵快速幂即可解决。
code time
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rl register ll
#define foa(i, a, b) for(rl i=a; i < b; ++ i)
#define fos(i, a, b) for(rl i=a; i <= b; ++ i)
#define fop(i, a, b) for(rl i=a; i >= b; -- i)
#define ws putchar(' ')
#define wl putchar('\n')
template <class T> inline void waw(T x)
{
if(x > 9) waw(x / 10);
putchar(x % 10 ^ 48);
}
template <class T> inline void ww(T x)
{
if(x < 0) x = ~x + 1, putchar('-');
waw(x);
}
template <class T> inline void read(T &res)
{
char ch = getchar(); bool f = 0; res = 0;
for(; !isdigit(ch); ch = getchar()) f |= ch == '-';
for(; isdigit(ch); ch = getchar()) res = (res << 1) + (res << 3) + (ch ^ 48);
res = f ? ~res + 1 : res;
}
const ll N = 55, P = 1e9 + 7;
ll n, m, k;
unordered_map<char, ll> mp;
struct Matrix
{
ll a[N][N];
Matrix () { memset(a, 0, sizeof a); }
Matrix operator *(const Matrix &x) const
{
Matrix res;
foa(i, 1, N) foa(k, 1, N) foa(j, 1, N)
res.a[i][j] = (res.a[i][j] + (a[i][k] * x.a[k][j]) % P) % P;
return res;
}
} ans, base;
inline void qmi(ll k)
{
while(k)
{
if(k & 1) ans = ans * base;
base = base * base; k >>= 1;
}
}
int main()
{
read(n), read(m), read(k);
fos(i, 0, 25) mp[(char)('a' + i)] = i + 1;
fos(i, 0, 25) mp[(char)('A' + i)] = i + 27;
fos(i, 1, m) ans.a[1][i] = 1;
fos(i, 1, m) fos(j, 1, m) base.a[i][j] = 1;
fos(i, 1, k)
{
char str[3]; cin >> str;
ll a, b;
a = mp[str[0]], b = mp[str[1]];
base.a[a][b] = 0;
}
qmi(n - 1);
ll res = 0;
fos(i, 1, m) res = (res + ans.a[1][i]) % P;
ww(res), wl;
return 0;
}