Modulo Sum of Increasing Sequences

AtCoder

IDarc145_f

Time4000ms

Memory256MB

Difficulty—

Find the number, modulo $998244353$, of non-decreasing sequences $A=(A_1,A_2,\ldots,A_N)$ of length $N$ consisting of integers between $0$ and $M$ (inclusive) that satisfy the following, for each $K=0,1,\ldots,\mathrm{MOD}-1$: * the sum of the elements in $A$ is congruent to $K$ modulo $\mathrm{MOD}$. What is a non-decreasing sequence? A sequence $B$ is non-decreasing if and only if $B_i \leq B_{i+1}$ for every integer ($1 \le i \le |B| - 1$), where $|B|$ is the length of $B$. ## Constraints * $1 \leq N ,M\leq 10^6$ * $1\leq \mathrm{MOD}\leq 500$ * All values in input are integers. ## Input Input is given from Standard Input in the following format: $N$ $M$ $\mathrm{MOD}$ [samples]

Samples

Input #1

2 2 4

Output #1

2 1 2 1

There are $6$ non-decreasing sequences of length $2$ consisting of integers between $0$ and $2$: $(0, 0), (0, 1),(0,2), (1,1),(1,2),(2,2)$. Here, we have:

*   $2$ sequences whose sums are congruent to $0$ modulo $4$: $(0,0),(2,2)$;
    
*   $1$ sequence whose sum is congruent to $1$ modulo $4$: $(0,1)$;
    
*   $2$ sequences whose sums are congruent to $2$ modulo $4$: $(0,2),(1,1)$;
    
*   $1$ sequence whose sum is congruent to $3$ modulo $4$: $(1,2)$.

Input #2

3 45 3

Output #2

5776 5760 5760

Input #3

1000000 1000000 6

Output #3

340418986 783857865 191848859 783857865 340418986 635287738

Print the counts modulo $998244353$.

API Response (JSON)

{
  "problem": {
    "name": "Modulo Sum of Increasing Sequences",
    "description": {
      "content": "Find the number, modulo $998244353$, of non-decreasing sequences $A=(A_1,A_2,\\ldots,A_N)$ of length $N$ consisting of integers between $0$ and $M$ (inclusive) that satisfy the following, for each $K=0",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 4000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "arc145_f"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Find the number, modulo $998244353$, of non-decreasing sequences $A=(A_1,A_2,\\ldots,A_N)$ of length $N$ consisting of integers between $0$ and $M$ (inclusive) that satisfy the following, for each $K=0...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments