Game

AtCoder

IDfps_24_s

Time5000ms

Memory256MB

Difficulty—

We define the following as a **subproblem**: > You are given a tree with $N$ vertices labeled $1$ through $N$, and an integer $K$ where $K=1$ or $K=N$. > Alice and Bob play a game with the following rules: > > * First, Alice places a piece on one of the vertices $1, 2, \dots, K$. > * Then, starting with Bob, they alternately perform the following operation: > * Choose a vertex adjacent to the current piece that has not yet been visited, and move the piece there. > * The player who cannot make a move on their turn loses, and the other player wins. > > Assuming both play optimally, determine who wins the game. You are given an integer $U$ and a value $\mathrm{type} \in {1, 2}$. For each $N = 2, 3, \dots, U$, solve the following problem: * You are given integers $N$ and $K$, where $K = 1$ if $\mathrm{type} = 1$, and $K = N$ if $\mathrm{type} = 2$. Suppose these values match the $N$ and $K$ of the subproblem above. There are $N^{N-2}$ possible trees with $N$ vertices labeled $1$ through $N$. Among them, count how many trees yield the answer "Alice" for the subproblem, and output the result modulo $998244353$. ## Constraints * $2 \leq U \leq 2.5 \times 10^5$ * $\mathrm{type} \in {1, 2}$ * All input values are integers ## Input The input is given from standard input in the following format: $U$ $\mathrm{type}$ ## Scoring This problem has the following scoring rules: * If you solve all datasets with $\mathrm{type} = 1$, you will earn $3$ points. * If you solve all datasets with $\mathrm{type} = 2$, you will earn $3$ points. [samples]

Samples

Input #1

4 1

Output #1

0
2
3

When $\mathrm{type} = 1$, $K = 1$ always holds.  
For $N = 3$, there are $2$ valid trees: one with edges $1-2-3$, and another with edges $1-3-2$.

Input #2

10 2

Output #2

0
3
4
125
576
16807
154624
4782969
69760000

When $\mathrm{type} = 2$, $K = N$ always holds.

API Response (JSON)

{
  "problem": {
    "name": "Game",
    "description": {
      "content": "We define the following as a **subproblem**: > You are given a tree with $N$ vertices labeled $1$ through $N$, and an integer $K$ where $K=1$ or $K=N$.   > Alice and Bob play a game with the followin",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 5000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "fps_24_s"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "We define the following as a **subproblem**:\n\n> You are given a tree with $N$ vertices labeled $1$ through $N$, and an integer $K$ where $K=1$ or $K=N$.  \n> Alice and Bob play a game with the followin...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments