行列の累乗で計算する。
1 日目と n + 1 日目は同じ移動パターンは同じになるので、(1〜n日目の繰り返し) * (1〜m日まで)を計算すればいい。
繰り返し部分は累乗で計算し、残りを掛け算すれば答えになる。
ただ、愚直に行列の計算をやるとTLEは必至だが、行列が巡回行列なので、最初の1行だけあれば計算できる。
巡回行列なんて初めて聞いた単語だったけど、
c[ i ][ j ] += a[ i ][ k ] * b[ k ][ j ] の i を 0 にして置き換えたら式が分かった。
しかし、以下の実装だとそれなりに遅い。
累乗の計算を再帰せずにやったとしても、行列の掛け算を(0〜n-1)、(0〜m-1)の2つに分けると間に合わない。
(0〜m-1)の時点で別の変数を使って残りを計算する、としている人がいたので真似てみた。
そしたら間に合った。
const int mod = 1000000007; vector<int> E; inline vector<int> mult(const vector<int>& a, const vector<int>& b) { const int N = a.size(); vector<int> c(N, 0); for (int k = 0; k < N; ++k) { if (a[k] == 0) continue; for (int j = 0; j < N; ++j) { c[j] += ((lli)a[k] * (lli)b[(N + k - j) % N]) % mod; c[j] %= mod; } } return c; } inline vector<int> pow(vector<int> v, lli p) { if (p == 0) return E; if (p == 1) return v; vector<int> u = pow(v, p / 2); if (p % 2) return mult(v, mult(u, u)); else return mult(u, u); } class PenguinEmperor { public: int countJourneys(int numCities, long long daysPassed) { const int N = numCities; E.resize(N, 0); E[0] = 1; const int M = N + 5; vector<int> move[M]; for (int day = 0; day < M; ++day) { move[day].resize(N, 0); move[day][day % N] = 1; move[day][(N - (day % N)) % N] = 1; } lli p = daysPassed / numCities; int q = daysPassed % numCities; vector<int> v = E; for (int i = 0; i < q; ++i) { v = mult(v, move[i + 1]); } vector<int> u = v; for (int i = q; i < N; ++i) { u = mult(u, move[i + 1]); } u = pow(u, p); return mult(v, u)[0]; } };