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