問題一覧 > 通常問題

No.1080 Strange Squared Score Sum

レベル : / AI推定難易度 : 2600 / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 16
作問者 : tko919 / テスター : yosupot
お気に入りにしたユーザー ProblemId : 4119 / 自分の提出
問題文最終更新日: 2020-06-12 21:37:42
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 252 (順位表) の他の問題:

Problem Statement

yuki is trying to fill $N$ cells arranged in a row with integers from $0$ to $N$. Specifically, the following operation is performed.

  1. Choose one integer $M$ between $0$ and $N$, inclusive.
  2. Write $0$ in $N-M$ distinct cells. Here, operations that differ in the order of writing $0$ are distinguished.
  3. Write natural numbers from $1$ to $N$ in the other $M$ cells. The sum of the written integers must be $K$. Also, operations that differ in the order of writing in the $M$ cells are not distinguished.
  4. For the integer $A_i$ written in the $i$-th cell, the square of the product of all $A_i+1$ is the "score" of the operation. However, when $M \bmod 4$ is $2$ or $3$, the score is multiplied by $-1$.
For each of $K=1,2, \cdots ,N$, find the sum of the "scores" obtained over all operations yuki can perform. Since the answer can be very large or negative, output it $\bmod 10^9+9$.

Input

$N$

$N$ is a natural number.
$1 \le N \le 10^5$

Output

Output the answers to the problem for $K=1,2, \cdots ,N$ in order, separated by newlines.

Sample

Sample 1
Input
3
Output
24
6
999999825

When $K=2$, the following $9$ operations can be performed.

  • There are $6$ ways to write $0$ in $2$ cells and $2$ in the remaining cell, and the score is $9$.
  • There are $3$ ways to write $0$ in $1$ cell and $1$ in the remaining cells, and the score is $-16$.
Therefore, the sum of the "scores" is $9 \times 6 + (-16) \times 3 = 6$.

Sample 2
Input
10
Output
14515200
3628800
888716809
488944009
572188178
240216987
181447707
619221884
695987525
438850637

Note that the output must be $\bmod 10^9+9$.

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