mayoko’s diary

プロコンとかいろいろ。

SRM 566 div1 med: PenguinEmperor

解法

入力の名前が長いので, n, m とします。
見た目からして行列累乗っぽい感じがします。

具体的には, まず dp[i][j] = (i 日目に場所 j にいるような場合の数) というのを i <= n についてやります。任意の i について, i 日目の移動の仕方は, i%n 日目のものと一致するので, これだけ調べれば十分です。

で, それを調べ終わったら m/n 回分の行列の掛け算, それと m%n 回分の移動を合わせて答えに組み込めば OK という感じです。

ただ, 今回は n の制約が大きいので行列累乗して O(n^3 log m) にすると危なそうです。ですが, 今回の問題では i -> i+k に移動するような場合の数は, i の値にかかわらず一定になるので, わざわざ行列を作らなくても良く, O(n^2) で計算できます。具体的には,

vector<ll> mul(vector<ll> a, vector<ll> b) {
    int n = a.size();
    vector<ll> ret(n);
    for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) {
        (ret[(i+j)%n] += a[i] * b[j] % MOD) %= MOD;
    }
    return ret;
}

このようにすれば良いです。

const int MAXN = 355;
const int MOD = 1e9+7;
ll dp[MAXN][MAXN];

vector<ll> mul(vector<ll> a, vector<ll> b) {
    int n = a.size();
    vector<ll> ret(n);
    for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) {
        (ret[(i+j)%n] += a[i] * b[j] % MOD) %= MOD;
    }
    return ret;
}

class PenguinEmperor {
public:
    int countJourneys(int n, long long m) {
        memset(dp, 0, sizeof(dp));
        // numCities 後 0 から i に行く場合の数を数える
        dp[0][0] = 1;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int cw = (j+i+1)%n;
                int ccw = (j-i-1+n)%n;
                (dp[i+1][cw] += dp[i][j]) %= MOD;
                if (cw != ccw) {
                    (dp[i+1][ccw] += dp[i][j]) %= MOD;
                }
            }
        }
        ll r = m/n, q = m%n;
        // r 回は累乗っぽいことをやる
        vector<ll> t(n), tn(n);
        for (int i = 0; i < n; i++) {
            t[i] = dp[q][i];
            tn[i] = dp[n][i];
        }
        for (int i = 0; i <= 60; i++) {
            if ((r>>i)&1) {
                t = mul(t, tn);
            }
            tn = mul(tn, tn);
        }
        return t[0];
    }
};