問題一覧 > 通常問題

No.1886 Sum of Slide Max

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 89
作問者 : miscalcmiscalc / テスター : 👑 ygussanyygussany ShirotsumeShirotsume
6 ProblemId : 6947 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-02-04 20:17:56

問題文

$(1, 2, \ldots, N)$ の順列 $P = (P_1, P_2, \ldots, P_N)$ と、$1 \leq K \leq N$ を満たす整数 $K$ に対し、$f_K(P)$ を次式で定義します。

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

$K = 1, 2, \ldots, N$ のそれぞれについて、次の問題を解いてください。

  • 順列 $P$ として考えられるものは $N!$ 通りあるが、そのすべてについて $f_K(P)$ を計算し、その総和を $998244353$ で割った余りを出力せよ。

入力

$N$

  • $N$ は整数である
  • $1 \leq N \leq 2 \times 10^5$

出力

$N$ 行出力してください。$i$ 行目には、$K = i$ の場合における問題の答えを出力してください。最後に改行してください。

サンプル

サンプル1
入力
3
出力
36
32
18

たとえば $K = 2$ の場合を考えると、

  • $P = (1, 2, 3)$ のとき、$f_2(P) = \max\{1, 2\} + \max\{2, 3\} = 2 + 3 = 5$
  • $P = (1, 3, 2)$ のとき、$f_2(P) = \max\{1, 3\} + \max\{3, 2\} = 3 + 3 = 6$
  • $P = (2, 1, 3)$ のとき、$f_2(P) = \max\{2, 1\} + \max\{1, 3\} = 2 + 3 = 5$
  • $P = (2, 3, 1)$ のとき、$f_2(P) = \max\{2, 3\} + \max\{3, 1\} = 3 + 3 = 6$
  • $P = (3, 1, 2)$ のとき、$f_2(P) = \max\{3, 1\} + \max\{1, 2\} = 3 + 2 = 5$
  • $P = (3, 2, 1)$ のとき、$f_2(P) = \max\{3, 2\} + \max\{2, 1\} = 3 + 2 = 5$
ですから、求める値は $5 + 6 + 5 + 6 + 5 + 5 = 32$ となります。

サンプル2
入力
5
出力
1800
1920
1620
1152
600

たとえば $K = 3, P = (4, 1, 2, 5, 3)$ のとき、$f_3(P) = \max\{4, 1, 2\} + \max\{1, 2, 5\} + \max\{2, 5, 3\} = 4 + 5 + 5 = 14$ です。

サンプル3
入力
12
出力
427083739
743823315
783415762
911798228
585453527
427083739
748039904
723050469
455899114
12629999
435516917
756797435

$998244353$ で割った余りを出力してください。

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