ほむほむほむら [yukicoder No.840]

https://yukicoder.me/problems/no/840

前提知識

• 行列累乗によるDP高速化
• DPテク11「文字列の部分列の個数を添え字に持つ典型」

解説

https://yukicoder.me/submissions/352662

Nが大きい、かつ、数え上げということなので、まずは行列累乗路線で考える。
「ほむら」のを作っていくが、DPテクとして「文字列の部分列の個数を添え字に持つ典型」というのがある。
これで
dp[i][ho][homu][homura] := i文字目まで確定していて、「ほ」がho個、「ほむ」がhomu個、「ほむら」がhomura個ある組み合わせ
今回はmodKで考えればいいので、状態はO(NK^3)。
当然無理だが、N以外を考えるとO(K^3)である。
これは現実的であり、遷移の係数はすべてのiについて同じであるので、行列累乗できそうだ。
　
K^3×K^3の行列を使って、K^3のベクタを更新する。
あとは、実装を頑張るだけだが、enc関数を作るのをおすすめする。

int N, K;
//---------------------------------------------------------------------------------------------------
int enc(int ho, int homu, int homura) {
	return ho * K * K + homu * K + homura;
}
//---------------------------------------------------------------------------------------------------
void _main() {
	cin >> N >> K;
	Mat m(K * K * K, Vec(K * K * K, 0));
	Vec v(K * K * K, 0);

	v[enc(0, 0, 0)] = 1;
	rep(ho, 0, K) rep(homu, 0, K) rep(homura, 0, K) {
		// ほ
		m[enc((ho + 1) % K, homu, homura)][enc(ho, homu, homura)] += 1;

		// む
		m[enc(ho, (homu + ho) % K, homura)][enc(ho, homu, homura)] += 1;

		// ら
		m[enc(ho, homu, (homura + homu) % K)][enc(ho, homu, homura)] += 1;
	}

	m = fastpow(m, N);
	v = mulMatVec(m, v);
	int ans = 0;
	rep(ho, 0, K) rep(homu, 0, K) ans = (ans + v[enc(ho, homu, 0)]) % mod;
	cout << ans << endl;
}