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; }