問題

$N + 1$ 個のマスがあり、次のようである:

  • $0, 1, \dots, N$ と番号が振られている
  • 最初すべてのマスには駒が置かれている

数列 $A$ であって次のようなものを考える:

  • 長さ $ A = K$
  • 要素は整数で $1 \le A_i \le N$
  • 要素はすべて異なる

数列 $A$ に対する点数を次のように定める:

  1. $i = 1, 2, \dots, K$ の順番に、マス $A_i$ にある駒をすべてマス $A_i−1$ に移す
  2. すべての駒についてその置かれているマスの番号を (重複なく) 考え、その総和が点数

条件を満たすすべての数列に対する点数の総和を $\bmod 10^9 + 7$ で求めよ。

考察

  1. とりあえず $N = K$ の場合を考えたい
  2. Many Shifts Hard があるということは、これらの問題の差が「Easy を解ける問題に変えている要素」である
  3. 確率を使う系だったりしないか
  4. ~~重複を許して長さ $K = A $ を増やすと数列 $A$ ごとの期待値は $\frac{N}{2}$ に近付きそう~~
    • 問題を勘違い。行き先を $A_i$ で指定するとかではなく位置 $A_i$ のものをひとつ下にずらす
  5. 元々 $x$ にあったものが $y \lt x$ に移って終了する確率を考えればよさそう
    • $x, x - 1, \dots, y + 1$ がこの順で数列 $A$ に含まれ、その後ろには $y$ が出てこない場合がそれ
  6. 元々 $x$ にあったものに対する移動が発生する回数の期待値を考えるのはどうか
    • 「その後ろには $y$ が出てこない」の条件が面倒そうなので、計測の位置を分配して解消したいため
  7. $d$ 回以上移動をする確率を考えたとき、不可能な場合を除いてその始点がどこかは影響しない
  8. 数列 $A$ 中に列 $1, 2, \dots, l$ が含まれる確率は ${} _ K C _ l \cdot {} _ {N - l} P _ {K - l} / {} _ N P _ K$
  9. 解けたはず
  10. 誤読が判明: 点数計算のときに同じマスに複数個の駒が置かれていても $1$ 個分しか考えない
  11. 各マスについて、そこが使われる期待値を求めたい
  12. あるマス $x$ に $x$ 由来の駒が残る確率と $x + 1$ 由来の駒が来る確率は独立ではない
  13. あるマス $x$ が使われるとは、$x$ が $A$ 中に出現しない、または $x$ が出現するがその後 $x + 1$ も出現する
  14. これやるだけじゃん (完)

解法

あるマス $x$ に駒がある状態で終了するのは「$x$ が $A$ 中に出現しない」または「$x$ が出現するがその後 $x + 1$ も出現する」場合のみ。 これらの確率は $1 - \frac{k}{n}$ と ${} _ K C _ 2 \cdot {} _ {N - 2} P _ {K - 2} / {} _ N P _ K$ であり、独立ではないが背反なので和を取ることができる。 確率は $x$ の値にほぼ依存せず、順列 ${} _ n P _ r$ の計算も $O(1)$ とみなせるので、全体での計算量は $O(1)$ となる。

反省

  • 誤読
    • サンプルを確認しましょう

誤読

多すぎて面白いのでまとめておく

リンク