SRM 661 div1 med: ColorfulLineGraphs
オチがそれかよって感じだった。解けなかったの悔しいですね。
解法
見た目的に漸化式作って行列累乗でもやるのか(実際には行列累乗はしませんが)という趣があるので漸化式を考えます。
n-1個の点を作る方法がp[n-1]通りあるとすると,p[n]は以下のようにして構成することが出来ます。
n-1個の色を並べている時点でK種類の色が,個あるとする。
すると,1種類目の色をn個目の頂点の色として塗ると,辺の構成の仕方は辺を構成しないという1通りと,自分の色以外に辺を1本伸ばす通りの合計通り。
同様に考えてすべての和を取ると,
通り。
これはに依存していないので任意の場合に成り立つ。よって,
p[n] = ((K-1)n+1)*p[n-1]が求めたかった漸化式です。しかし,これは行列累乗の形に持ち込むことは出来ません。よって,別の方法を考える必要があります。ここからのオチが最高です。
とりあえず漸化式をもっと一般化してみると,
p[n] = ((K-1)+1) * (2*(K-1)+1) * ... * (n*(K-1)+1)
と書けることがわかります。掛け算する数が等差(K-1)になっていることがわかります。
Mの制約が小さいことに注目すると,上の掛け算は周期Mで回るはずなので,その周期性を利用することで答えを求めることが出来ます。
ll powmod(ll x, ll p, ll m) { //if (x == 0) return 0; if (p == 0) return 1; if (p%2) { return (powmod(x, p-1, m) * x) % m; } else { ll tmp = powmod(x, p/2, m); return (tmp*tmp)%m; } } class ColorfulLineGraphs { public: int countWays(long long N, long long K, int M) { ll tmp = 1; for (int i = 1; i <= M; i++) { tmp *= (((K-1)%M)*i+1); tmp %= M; } ll q = N%M; ll x = 1; for (int i = 1; i <= q; i++) { x *= (((K-1)%M)*i+1); x %= M; } ll p = N/M; cout << tmp << " " << x << endl; return (powmod(tmp, p, M) * x) % M; } };