問題一覧 > 通常問題

No.1886 Sum of Slide Max

レベル : / AI推定難易度 : 1700 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 92
作問者 : miscalc / テスター : ygussany Shirotsume
お気に入りにしたユーザー ProblemId : 6947 / 自分の提出
問題文最終更新日: 2022-02-04 20:17:56
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 337 (順位表) の他の問題:

Problem Statement

For a permutation $P = (P_1, P_2, \ldots, P_N)$ of $(1, 2, \ldots, N)$ and an integer $K$ satisfying $1 \leq K \leq N$, define $f_K(P)$ by the following formula.

$$\displaystyle f_K(P) = \sum_{i = 1}^{N - K + 1} \max \{P_i, P_{i+1}, \ldots, P_{i + K - 1} \}$$

Solve the following problem for each of $K = 1, 2, \ldots, N$.

  • There are $N!$ possible permutations $P$. Compute $f_K(P)$ for all of them, and output the sum of these values modulo $998244353$.

Input

$N$

  • $N$ is an integer.
  • $1 \leq N \leq 2 \times 10^5$

Output

Output $N$ lines. On the $i$-th line, output the answer to the problem for the case $K = i$. Print a newline at the end.

Sample

Sample 1
Input
3
Output
36
32
18

For example, consider the case $K = 2$.

  • When $P = (1, 2, 3)$, $f_2(P) = \max\{1, 2\} + \max\{2, 3\} = 2 + 3 = 5$
  • When $P = (1, 3, 2)$, $f_2(P) = \max\{1, 3\} + \max\{3, 2\} = 3 + 3 = 6$
  • When $P = (2, 1, 3)$, $f_2(P) = \max\{2, 1\} + \max\{1, 3\} = 2 + 3 = 5$
  • When $P = (2, 3, 1)$, $f_2(P) = \max\{2, 3\} + \max\{3, 1\} = 3 + 3 = 6$
  • When $P = (3, 1, 2)$, $f_2(P) = \max\{3, 1\} + \max\{1, 2\} = 3 + 2 = 5$
  • When $P = (3, 2, 1)$, $f_2(P) = \max\{3, 2\} + \max\{2, 1\} = 3 + 2 = 5$
Therefore, the required value is $5 + 6 + 5 + 6 + 5 + 5 = 32$.

Sample 2
Input
5
Output
1800
1920
1620
1152
600

For example, when $K = 3, P = (4, 1, 2, 5, 3)$, we have $f_3(P) = \max\{4, 1, 2\} + \max\{1, 2, 5\} + \max\{2, 5, 3\} = 4 + 5 + 5 = 14$.

Sample 3
Input
12
Output
427083739
743823315
783415762
911798228
585453527
427083739
748039904
723050469
455899114
12629999
435516917
756797435

Output the values modulo $998244353$.

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