問題一覧 > 通常問題

No.2944 Sigma Partition Problem

レベル : / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 57
作問者 : kazuppa / テスター : 👑 seekworser Magentor hirayuu_yc
0 ProblemId : 11364 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-11-20 19:52:34

ストーリー

一般に引き裂くものといえばカップルとかですが、天才数学者のkazuppaくんは引き裂くものといえば数らしいです。

問題文

ある正整数からなる数列 x1,x2...x∣x∣x_1,x_2...x_{|x|} が次の条件をすべて満たすとき、 xx は mm の分割であるとします。

  • xi≥xi+1(1≤i≤∣x∣−1)x_i\geq x_{i+1} (1\leq i\leq |x|-1)

  • ∑i=1∣x∣xi=m\displaystyle\sum_{i=1}^{|x|}x_i=m

    • たとえば、 (3,2,1)(3,2,1) や (2,2,2)(2,2,2) 、 (6)(6) は 66 の分割であると言えます。

    一方で、 (2,3,4)(2,3,4) や (2,2,2,2)(2,2,2,2) 、 (3,3,3,0)(3,3,3,0) は 99 の分割とは言えません。

    また、 M(n,k)M(n,k) と L(n,k)L(n,k) を次のように定義します。

  • M(n,k)=nM(n,k) = n の分割のうち、最大値が kk であるものの個数

  • L(n,k)=nL(n,k) = n の分割のうち、長さが kk であるものの個数

    • QQ 個のクエリが与えられます。順に処理してください。

  • 1 n k ∑i=1kM(n,i) mod 998244353\displaystyle\sum_{i=1}^k M(n,i)\bmod{998244353} を出力してください。

  • 2 n k ∑i=1kL(n,i) mod 998244353\displaystyle\sum_{i=1}^k L(n,i)\bmod{998244353} を出力してください。

    • 入力

    入力は以下の形式で標準入力から与えられる。 
    QQ
Query1Query_1
Query2Query_2
.
.
.
QueryQQuery_Q
    また、各 QQ 個のクエリは次のうちのどちらかの方法で与えられる。 
    1 n k1\ n\ k
    2 n k2\ n\ k

    制約

    • 1≤Q≤1\leq Q\leq 100100
    • 1≤ni,ki≤4000 (1≤i≤Q)1\leq n_i,k_i\leq 4000\ (1\leq i\leq Q)
    • 入力はすべて整数

    出力

    ii 行目には ii 番目のクエリの指示に従ってください。 最後に改行してください。

    サンプル

    サンプル1
    入力
    2
1 5 2
2 3 3
    出力
    3
3

    各クエリに対する答えは次のようになります。

  • 11 番目のクエリは 55 の分割で最大値が 22 以下になるものの個数です。

    •     \ \ \ \ この条件を満たすのは (2,2,1),(2,1,1,1),(1,1,1,1,1)(2,2,1),(2,1,1,1),(1,1,1,1,1) の 33 つです。

  • 22 番目のクエリは 33 の分割で長さが 33 以下になるものの個数です。

    •     \ \ \ \ この条件を満たすのは (3),(2,1),(1,1,1)(3),(2,1),(1,1,1) の 33 つです。

    サンプル2
    入力
    6
2 300 20
1 128 15
2 26 7
1 13 7
1 26 4
2 51 29
    出力
    50990369
459046796
1009
82
206
236437

    答えを 998244353998244353 で割った余りで求めることに注意してください。

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