No.2575 Almost Increasing Sequence
タグ : / 解いたユーザー数 23
作問者 :
hotman78
/ テスター :
noshi91
注意
本問はスコア問題ですが，最高得点が存在し，想定解にて最高得点を得ることが出来ます.
ただし，この問題の実行時間制限が厳しいので，最高得点を目指す場合高速な言語の利用を強く推奨します．
writer 解, tester 解の言語はともに C++ で，実行時間はそれぞれ 4024 ms, 673 ms です．
問題文
最初に非負整数 $K$ が与えられ，以下の様に数列 $(A_1, A_2, A_3, \dots )$ を定めます．
- $A_n$ : 最長減少部分列の長さが $3$ であるような全ての要素数 $n$ の順列に対し，最長増加部分列の長さを $K$ 乗した値の総和を $998244353$ で割ったあまり
$30000$ 以下の正整数 $N$ を一つ決め， $N$ 以下の正整数 $n$ に対し $A_n$ をそれぞれ求めてください．
採点方法
一ケースあたりの貴方の得点は $N$ 点となります．また，テストケースは全部で $20$ 個あり，全テストケースの得点の合計が提出の得点となります．
ただし，出力が不正である場合は WA と判定され，AC 以外の判定を一つ以上のテストケースで得た解答の得点は $0$ 点となります．不正な出力とは以下を指します．
- 出力形式に従わなかった
- 誤った出力内容を出力した
コンテスト時間中に得た最高得点で最終順位が決定され，コンテスト期間終了後のリジャッジ，システムテスト等は予定しておりません．
制約
- $0 \leq K \leq 10^9$
- 入力は全て整数で与えられる
入力
$K$
出力
$N$
$A_1\ A_2 \dots A_{N}$
サンプル
サンプル1
入力
100
出力
4 0 0 1 954786991
長さが $2$ 以下の順列であって最長減少部分列の長さが $3$ である物は存在しません．
長さが $3$ の順列であって最長減少部分列の長さが $3$ であるのは $(3, 2, 1)$ のみでありこの順列の最長増加列の長さは $1$ であるため，$A_3= 1^{100}=1$ となります
長さが $4$ の順列であって最長減少部分列の長さが $3$ であるのは $(1, 4, 3, 2), (2, 4, 3, 1), (3, 2, 1, 4), (3, 2, 4, 1), (3, 4, 2, 1), (4, 1, 3, 2), (4, 2, 1, 3),(4, 2, 3, 1),(4, 3, 1, 2)$ の $9$ 通り存在し，いずれも最長増加部分列の長さは $2$ となるので，$A_4 \equiv 9 \times 2^{100} \equiv 954786991 \pmod {998244353}$ となります．
このテストケースに対し，この解答を提出した場合 $4$ 点が得られます．
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。