SRM 661 div1 med: ColorfulLineGraphs

オチがそれかよって感じだった。解けなかったの悔しいですね。

問題

TopCoder Statistics - Problem Statement

解法

見た目的に漸化式作って行列累乗でもやるのか(実際には行列累乗はしませんが)という趣があるので漸化式を考えます。

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