問題一覧 > 通常問題

No.1080 Strange Squared Score Sum

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 15
作問者 : tko919tko919 / テスター : yosupotyosupot
0 ProblemId : 4119 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2020-06-12 21:37:42

問題文

yukiさんは一列に並んだ $N$ 個のマスを $0$ から $N$ の整数で埋めようとしています。具体的には次の操作に則ります。

  1. $0$ 以上 $N$ 以下の整数 $M$ を一つ定める。
  2. 相異なる $N-M$ 個のマスに $0$ を書き込む。ただし, $0$ を書き込む順番が異なる操作は区別する。
  3. 他の $M$ マスに $1$ から $N$ の自然数を書き込む。書き込んだ整数の総和は $K$ でなければならない。また、 $M$ マスに書き込む順番が異なる操作は区別されない。
  4. $i$ マス目に書かれた整数 $A_i$ について、 $A_i+1$ の総積の二乗をその操作の「スコア」とする。しかし、 $M \bmod 4$ が $2$ または $3$ のときスコアは $-1$ 倍される。
$K=1,2, \cdots ,N$ のそれぞれについて、yukiさんが行うことのできる全ての操作によって得られる「スコア」の総和を求めてください。ただし、答えは非常に大きくなる、もしくは負になる可能性があるため、 $\bmod 10^9+9$ で出力してください。

入力

$N$

$N$ は自然数
$1 \le N \le 10^5$

出力

$K=1,2, \cdots ,N$ に対する問題の答えを、順番に改行区切りで出力せよ。

サンプル

サンプル1
入力
3
出力
24
6
999999825

$K=2$ のとき、行うことのできる操作は以下の $9$ 通りです。

  • $2$ つのマスに $0$ 、残りのマスに $2$ を書き込む方法は $6$ 通りあり、スコアは $9$ です。
  • $1$ つのマスに $0$ 、残りのマスに $1$ を書き込む方法は $3$ 通りあり、スコアは $-16$ です。
よって、「スコア」の総和は $9 \times 6 + (-16) \times 3 = 6$ です。

サンプル2
入力
10
出力
14515200
3628800
888716809
488944009
572188178
240216987
181447707
619221884
695987525
438850637

$\bmod 10^9+9$ で出力することに注意してください。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。