問題一覧 > 通常問題

No.2944 Sigma Partition Problem

レベル : / AI推定難易度 : 1450 / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 58
作問者 : kazuppa / テスター : 👑 seekworser Magentor hirayuu_yc
お気に入りにしたユーザー ProblemId : 11364 / 自分の提出
問題文最終更新日: 2024-11-20 19:52:34
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 450 (順位表) の他の問題:

Story

Generally, when people talk about things that get torn apart, they mean couples and the like, but for the genius mathematician kazuppa, the things that get torn apart are apparently numbers.

Problem Statement

When a sequence consisting of positive integers $x_1,x_2...x_{|x|}$ satisfies all of the following conditions, $x$ is said to be a partition of $m$.

  • $x_i\geq x_{i+1} (1\leq i\leq |x|-1)$
  • $\displaystyle\sum_{i=1}^{|x|}x_i=m$
  • For example, $(3,2,1)$, $(2,2,2)$, and $(6)$ are partitions of $6$.

    On the other hand, $(2,3,4)$, $(2,2,2,2)$, and $(3,3,3,0)$ are not partitions of $9$.

    Also, define $M(n,k)$ and $L(n,k)$ as follows.

  • $M(n,k) = n$'s number of partitions whose maximum value is $k$
  • $L(n,k) = n$'s number of partitions whose length is $k$
  • You are given $Q$ queries. Process them in order.

  • 1 n k Output $\displaystyle\sum_{i=1}^k M(n,i)\bmod{998244353}$.
  • 2 n k Output $\displaystyle\sum_{i=1}^k L(n,i)\bmod{998244353}$.
  • Input

    The input is given from standard input in the following format.
    $Q$
    $Query_1$
    $Query_2$
    .
    .
    .
    $Query_Q$
    
    Each of the $Q$ queries is given in one of the following forms.
    $1\ n\ k$
    $2\ n\ k$

    Constraints

    • $1\leq Q\leq $ $100$
    • $1\leq n_i,k_i\leq 4000\ (1\leq i\leq Q)$
    • All inputs are integers

    Output

    On line $i$, follow the instruction of the $i$-th query. Print a newline at the end.

    Sample

    Sample 1
    Input
    2
    1 5 2
    2 3 3
    
    Output
    3
    3
    

    The answer to each query is as follows.

  • Query $1$ asks for the number of partitions of $5$ whose maximum value is at most $2$.
  • $\ \ \ \ $The partitions satisfying this condition are the $(2,2,1),(2,1,1,1),(1,1,1,1,1)$, $3$ in total.

  • Query $2$ asks for the number of partitions of $3$ whose length is at most $3$.
  • $\ \ \ \ $The partitions satisfying this condition are the $(3),(2,1),(1,1,1)$, $3$ in total.

    Sample 2
    Input
    6
    2 300 20
    1 128 15
    2 26 7
    1 13 7
    1 26 4
    2 51 29
    
    Output
    50990369
    459046796
    1009
    82
    206
    236437
    

    Note that the answer must be computed modulo $998244353$.

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