-
长度为 n，并且只包含字符 1∼m (n≤1e15,m≤52)
-
满足 K 个要求，第 i 个要求为 xi 后面不能是 yi
现在问你，有多少种字符串符合条件。
F[ i ][ j] += F[i -1] [lk ]* a[k][j]
用矩阵快速幂优化
即 F[1] *ksm( a, n-1)
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#define IOS std::ios::sync_with_stdio(0)
using namespace std;
const int N =1e5+5,mod=1e9+7;
#define int long long
bool ch[55][53];
int n,m,K;
struct matrix {
int a[52+2][52+2];
};
matrix m1;
void init_(matrix &x){
int i,j;
for(i=1;i<=m;i++)
for(j=1;j<=m;j++) {
x.a[i][j]=0;
if(i==j) x.a[i][j]=1;
}
}
matrix mul(matrix &x,matrix &y){
int i,j,k;
matrix z;
for(i=1;i<=m;i++)
for(j=1;j<=m;j++){
z.a[i][j]=0;
for(k=1;k<=m;k++)
z.a[i][j]+=x.a[i][k]*y.a[k][j]%mod, z.a[i][j]%=mod;
}
return z;
}
matrix ksm(matrix &x,int k){
matrix tmp=x, ans;
init_(ans);
while(k){
if(k&1) ans=mul(ans,tmp);
tmp=mul(tmp,tmp);
k/=2;
}
return ans;
}
signed main(){
cin>>n>>m>>K;
matrix Z;
int i,j;
for(i=1;i<=m;i++) for(j=1;j<=m;j++) Z.a[i][j]=1;
for(i=1;i<=K;i++){
char c1,c2 ;
cin>>c1>>c2;
if(c1>='a'&&c1<='z') c1-='a';
if(c2>='a'&&c2<='z') c2-='a';
if(c1>='A'&&c1<='Z') c1-='A',c1+=26;
if(c2>='A'&&c2<='Z') c2-='A',c2+=26;
Z.a[++c1][++c2]=0;
}
matrix F;
for(j=1;j<=m;j++) F.a[1][j] =1;
matrix tmp =ksm(Z,n-1) ;
F=mul(F,tmp);
int ans =0;
for(i=1;i<=m;i++)
ans+= F.a[1][i],ans%=mod;
cout<<ans<<endl;
}