TopCoder SRM 550 Div1 Hard ConversionMachine

問題

'a', 'b', 'c'からなる同じ長さの文字列word1, word2が与えられる。
word1の文字一つ選び、
aならbに
bならcに
cならaに変えるという操作を行う。

aをbに変える操作はcosts[0]が、
bをcに変える操作はcosts[1]が、
cをaに変える操作はcosts[2]がかかる。
合計のコストをmaxCost以下にして、word1をword2に変えるとき、
操作の仕方は何通りあるか、mod 10^9 + 7で求めよ。

制約条件

word1, word2の長さ≦11
costs[i]≦10^9
maxCosts≦10^9

方針

word1をword2に変化させる最低コストは簡単に求まる。
word2に変化させた上で、余分な操作を何度か繰りかえすと考えると、
この余分な操作1組にかかるコストは、どういう操作を行うかにかかわらず、
一組あたりcosts[0] + costs[1] + costs[2]で一定になることがわかる。

したがって、余分な操作は(maxCost - minCost) / (costs[0] + costs[1] + costs[2]) * 3
回だけ行える。
この操作回数以内で、word1をword2に変化させる場合の数を求めればよい。

word1の状態は、
あと2度の変化でword2の文字に一致する文字がd2文字、
あと1度の変化でword1の文字に一致する文字がd1文字ある状態を同一視してよく、

d1 * d2通りだけ考えればよい。
この状態に対して遷移行列を考えて、それを累乗すれば答えが求まる。

遷移は、
(d1, d2)→(d1 + 1, d2 - 1)
(d1, d2)→(d1 - 1, d2)
(d1, d2)→(d1, d2 + 1)
の3通りがある。
(d1, d2)の組とは別に、ゴールの頂点を作っておき、(0, 0)から移動できるようにしておく。
すると、操作が一定回数以内の場合の数の和が簡単に求められる。

ソースコード

typedef vector<vi> M;
class ConversionMachine {
	public:
	int countAll(string word1, string word2, vector <int> costs, int maxCost) {
		int n = word1.size();
		int d1 = 0, d2 = 0;
		ll minCost = 0, minmove = 0;
		
		rep(i, n){
			int a = word1[i] - 'a', b = word2[i] - 'a';
			if((a + 1) % 3 == b) d1++;
			if((a + 2) % 3 == b) d2++;
			while(a != b){
				minCost += costs[a];
				a = (a + 1) % 3;
				minmove++;
			}
		}
		if(minCost > maxCost) return 0;
		
		ll maxmove = (maxCost - minCost) / ((ll)costs[0] + costs[1] + costs[2]) * 3 + minmove;
		
		n++;
		M tmp(n * n, vi(n * n));
		vi to(n * n);
		int p = 0;
		rep(i, n) rep(j, n) if(i + j < n) to[i * n + j] = p++;
		
		M m(p + 1, vi(p + 1));
		rep(i, n) rep(j, n) if(i + j < n) {
			if(j && i < n - 1) m[to[i * n + j]][to[(i + 1) * n + j - 1]] = j;
			if(i) m[to[i * n + j]][to[(i - 1) * n + j]] = i;
			if(i + j < n - 1) m[to[i * n + j]][to[i * n + j + 1]] = n - i - j - 1;
		}
		m[0][p] = m[p][p] = 1;
		m = pow(m, maxmove + 1);
		ll res = m[to[d1 * n + d2]][p];
		return res;
	}
};