Xmas Contest 2017 D 問題 Inversion Number 解説

Xmas Contest 2017 D 問題「Inversion Number」の解説です。

問題概要

素数 N の順列であって、その転倒数を K で割った余りが m であるようなものの個数を 10^9 + 7 で割った余りを求めよ。

制約

  • 1 ≦ N ≦ 10^18
  • 0 ≦ m < K ≦ 10

解説

まず、N がさほど大きくない場合の解法を紹介します。この場合、

  • dp[n][k] := 長さ n の順列で、その転倒数を K で割った余りが k になるものの個数

という DP を行うことができます。長さ n の順列に新たに n+1 を挿入することを考えると、その挿入位置から転倒数の増分がすぐにわかるので、全体として以下のような DP になります。

dp[0][0] = 1;
for (int i = 0; i < N; ++i) {
  for (int j = 0; j < K; ++j) {
    for (int pos = 0; pos <= i; ++pos) {
      dp[i + 1][(j + pos) % K] += dp[i][j];
    }
  }
}

ここで、ちょうど K 番目の要素を挿入するときの DP 配列に注目しましょう(つまり、N=K となる場合の答えに注目します)。このときだけに注目すると DP 配列は次のように更新されています。

for (int mod = 0; mod < K; ++mod) {
  for (int pos = 0; pos < K; ++pos) {
    dp[K][(mod + pos) % K] += dp[K - 1][mod];
  }
}

これは、dp[K-1][mod] の値が、dp[K] の mod 番目、 (mod+1)%K 番目、(mod+2)%K 番目、……、(mod+K-1)%K 番目に足されているということで、結局 dp[K] の全体に1回ずつ足しているだけです。つまり、

  • dp[K][mod] = Σ_p dp[K-1][p]

が成り立ちます。この値は mod に依存していないので、N=K となる場合の答えは m に依存せずすべて同じであることがわかります。すなわち、N=K となる場合の答えは N! / K に他なりません。

さらに、このことに注意しながら N>K の場合を考えましょう。DP の更新式から、dp[n][mod] の値は dp[n-1] から n 個の値を持ってきて足し合わせたものになっていることがわかります。N=K のときに dp[K] の値はすべて同じになることがわかっているので、dp[K+1], dp[K+2], ..., もすべて mod に依らず同じ値を持つことになります。結局、N≧K となる場合の答えは N! / K であることがいえます。

ここまでくれば次のような解法でこの問題を解くことができます。

  • N < K のとき、N < K ≦ 10 なので DP や全探索によって解く。
  • N ≧ K のとき、N! / K を求める。

残った問題は N ≦ 10^18 のときに N! mod 10^9+7 をどう高速に求めるかという部分です。

N ≧ 10^9+7 のとき N! は 10^9+7 の倍数なので、当然 N! mod 10^9+7 = 0 となります。

N < 10^9+7 のとき、まだ O(N) かけていては間に合いません。そこで、N が何か適当な定数 (たとえば 500万とします) の倍数のときの N! mod 10^9+7 の値をあらかじめ求めてプログラム中にその結果をすべて埋め込んでおきます(これは手元で数秒〜数十秒程度の計算でできるはずです)。すると、任意の N < 10^9+7 に対しての N! の計算が高々 500 万回の掛け算で行えることになります(N 以下の 500 万の倍数で最大のものの階乗の値が埋め込んであるので、あとはそこから N までひとつずつ掛け算していく)。

以上でこの問題を十分高速に解くことができました。