問題一覧 > 通常問題

No.1886 Sum of Slide Max

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

問題文

(1,2,…,N) の順列 P=(P1,P2,…,PN) と、1≤K≤N を満たす整数 K に対し、fK(P) を次式で定義します。

fK(P)=∑i=1N−K+1max{Pi,Pi+1,…,Pi+K−1}

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

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

入力

N

  • N は整数である
  • 1≤N≤2×105

出力

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

サンプル

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

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

  • P=(1,2,3) のとき、f2(P)=max{1,2}+max{2,3}=2+3=5
  • P=(1,3,2) のとき、f2(P)=max{1,3}+max{3,2}=3+3=6
  • P=(2,1,3) のとき、f2(P)=max{2,1}+max{1,3}=2+3=5
  • P=(2,3,1) のとき、f2(P)=max{2,3}+max{3,1}=3+3=6
  • P=(3,1,2) のとき、f2(P)=max{3,1}+max{1,2}=3+2=5
  • P=(3,2,1) のとき、f2(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) のとき、f3(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もしくは右上の雲マークをクリックしてアカウントを作成してください。