問題一覧 > 通常問題

No.2944 Sigma Partition Problem

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

ストーリー

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

問題文

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

  • $x_i\geq x_{i+1} (1\leq i\leq |x|-1)$

  • $\displaystyle\sum_{i=1}^{|x|}x_i=m$

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

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

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

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

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

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

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

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

    • 入力

    入力は以下の形式で標準入力から与えられる。 
    $Q$
$Query_1$
$Query_2$
.
.
.
$Query_Q$
    また、各 $Q$ 個のクエリは次のうちのどちらかの方法で与えられる。 
    $1\ n\ k$
    $2\ n\ k$

    制約

    • $1\leq Q\leq $ $100$
    • $1\leq n_i,k_i\leq 4000\ (1\leq i\leq Q)$
    • 入力はすべて整数

    出力

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

    サンプル

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

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

  • $1$ 番目のクエリは $5$ の分割で最大値が $2$ 以下になるものの個数です。

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

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

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

    サンプル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

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

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