Bubble Cup8 Finals H. Bots

問題

概要

2台のロボットがある.
$2N$ターンのうちどちらかを$N$ターン,もう一台を$N$ターン動かすという処理を行う.
各ターンごとの状態数の総和を求めよ.

制約

  • $1 \le N \le 10^{6}$

解法

ナイーブにやってOEISに投げたら解けてしまった.
順列とその逆元を$O(N)$で構築して投げる.

コード

テンプレート部,ライブラリ部は省略する.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Solver
{
public void Solve()
{

var n = sc.Integer();
ModInteger ans = 0;
var table = new ModTable(2000050);

n += 1;
ans = 2 * table[2 * n - 1];
ans *= table.inv[n] * table.inv[n - 1];
IO.Printer.Out.WriteLine(ans - 1);
}
}

まとめ

OEISは偉大