SRM566 Div1 Medium

500

行列の累乗で計算する。
1 日目と n + 1 日目は同じ移動パターンは同じになるので、(1〜ｎ日目の繰り返し) * (1〜ｍ日まで)を計算すればいい。
繰り返し部分は累乗で計算し、残りを掛け算すれば答えになる。
ただ、愚直に行列の計算をやると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];
  }
};