Codeforces Round #137 (Div. 2) E : Decoding Genome

問題概要

サイズM(<52)のアルファベットがある。長さN(<10^15)の文字列で、複数の禁止パターンに合致しない文字列の個数を求める問題。禁止パターンは長さ2。

解法

末尾の文字を状態にして行列累乗でDPする。

acceptされたコード

#include <vector>
#include <cstdio>
#include <cctype>
using namespace std;

typedef long long int64;
typedef int64 mat_t;

const int64 MOD = (int64)( 1e9 + 7 );

struct Matrix : vector< vector<mat_t> > {
	int height, width;

	Matrix(){}
	Matrix(int height, int width):
		height(height), width(width)
	{
		assign(height, vector<mat_t>(width, 0));
	}
};

Matrix getIdentity(int size){
	Matrix ret(size, size);
	for (int i = 0; i < size; ++i) {
		ret[i][i] = 1;
	}
	return ret;
}

Matrix operator* (const Matrix& lhs, const Matrix& rhs) {
	Matrix ret(lhs.height, rhs.width);

	for (int i = 0; i < lhs.height; ++i) {
		for (int k = 0; k < lhs.width; ++k) {
			for (int j = 0; j < rhs.width; ++j) {
				ret[i][j] += lhs[i][k] * rhs[k][j];
				ret[i][j] %= MOD;
				if (ret[i][j] < 0) {
					ret[i][j] += MOD;
				}
			}
		}
	}

	return ret;
}

Matrix pow(const Matrix& x, const int64 k) {
	Matrix ret = getIdentity(x.width), base = x;

	for (int64 e = k; e; e >>= 1) {
		if (e&1) {
			ret = ret * base;
		}
		base = base * base;
	}

	return ret;
}

int64 N;
int M, K;
Matrix mat;

int toInt(char ch) {
	if (islower(ch)) {
		return ch - 'a';
	}
	else {
		return ch - 'A' + 26;
	}
}

int64 solve() {
	int64 ans = 0;
	mat = pow(mat, N-1);
	for (int i = 0; i < M; ++i) {
		for (int j = 0; j < M; ++j) {
			ans = (ans + mat[i][j]) % MOD;
		}
	}
	return ans;
}

void init() {
	scanf("%lld%d%d ", &N, &M, &K);
	char buf[0x100];
	mat = Matrix(M, M);
	for (int i = 0; i < M; ++i) {
		for (int j = 0; j < M; ++j) {
			mat[i][j] = 1;
		}
	}
	for (int _ = 0; _ < K; ++_) {
		scanf(" %s ", buf);
		mat[toInt(buf[0])][toInt(buf[1])] = 0;
	}
}

int main() {
	init();
	printf("%lld\n", solve());
	return 0;
}