Non-Adjacent Matching

AtCoder

IDarc156_e

Time4000ms

Memory256MB

Difficulty—

Find the number, modulo $998244353$, of **good sequences** of length $N$ whose elements are integers between $0$ and $M$, inclusive, and whose sum is at most $K$. Here, a length-$N$ sequence $X=(X_1,X_2,\ldots,X_N)$ is said to be good if and only if there is a graph $G$ that satisfies all of the following conditions. * $G$ is a graph with $N$ vertices numbered $1$ to $N$ without self-loops. (It may have multi-edges.) * For each $i\ (1\leq i \leq N)$, the degree of vertex $i$ is $X_i$. * For each $i\ (1\leq i \leq N)$, no edge connects vertex $i$ and vertex $i+1$. Here, vertex $N+1$ means vertex $1$. ## Constraints * $4 \leq N \leq 3000$ * $0 \leq M \leq 3000$ * $0\leq K \leq NM$ * All numbers in the input are integers. ## Input The input is given from Standard Input in the following format: $N$ $M$ $K$ [samples]

Samples

Input #1

4 1 2

Output #1

3

The following three sequences are good.

*   $(0,0,0,0)$
*   $(0,1,0,1)$
*   $(1,0,1,0)$

Input #2

10 0 0

Output #2

Input #3

314 159 26535

Output #3

248950743

Print the count modulo $998244353$.

API Response (JSON)

{
  "problem": {
    "name": "Non-Adjacent Matching",
    "description": {
      "content": "Find the number, modulo $998244353$, of **good sequences** of length $N$ whose elements are integers between $0$ and $M$, inclusive, and whose sum is at most $K$. Here, a length-$N$ sequence $X=(X_1,X",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 4000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "arc156_e"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Find the number, modulo $998244353$, of **good sequences** of length $N$ whose elements are integers between $0$ and $M$, inclusive, and whose sum is at most $K$.\nHere, a length-$N$ sequence $X=(X_1,X...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments