Codeforces 222 E. Decoding Genome

問題

m個のアルファベットからなる長さnのDNAの総数を求めよ。
ただし禁止パターンがk個あり、
禁止パターンは2文字の連続するアルファベットにより指定される。
（この順にアルファベットが出るDNAはだめだが、逆順に出るものはOK）

制約条件

n≦10^15
m≦52
k≦m * m

方針

行列の累乗するだけ。

ソースコード

const int mod = 1000000007;

typedef vector<vi> M;
M operator*(M &a, M &b){
	M c(a.size(), vi(b[0].size()));
	rep(i, c.size()) rep(j, c[0].size()){
		rep(k, b.size()){
			c[i][j] += (ll)a[i][k] * b[k][j] % mod;
			c[i][j] %= mod;
		}
	}
	return c;
}
M pow(M m, ll n){
	M res(m.size(), vi(m[0].size()));
	rep(i, m.size()) res[i][i] = 1;
	
	for(; n; n /= 2){
		if(n & 1) res = res * m;
		m = m * m;
	}
	return res;
}

int to(char c){
	if(islower(c)) return c - 'a';
	return c - 'A' + 26;
}

int main(){
	ll n, m, k;
	cin >> n >> m >> k;
	
	M ma(m, vi(m, 1));
	
	rep(i, k){
		string s; cin >> s;
		ma[to(s[0])][to(s[1])] = 0;
	}
	
	M x(m, vi(1, 1));
	ma = pow(ma, n - 1);
	x = ma * x;
	
	ll ans = 0;
	rep(i, m) ans += x[i][0];
	cout << ans % mod << endl;
	
	return 0;
}