E - Remove 2K+1 Edges Editorial /

Time Limit: 12 sec / Memory Limit: 1024 MB

配点 : 1800 点

問題文

正整数 N, K が与えられます。頂点に 1 から (2K + 1) N + 1 までの番号がついた (2K+1)N + 1 頂点の無向木 T のうち次の条件を満たすものの個数を 998244353 で割った余りを求めてください。

  • T に次の操作を繰り返し行うことで、T に含まれる辺を全て取り除くことが出来る。
    • 長さ 2K + 1 のパスを選び、パスに含まれる辺を全て取り除く。
      厳密に述べると、相異なる頂点の列 v_0, v_1, \dots, v_{2K+1} であって 0 \leq i \leq 2K を満たす全ての i について辺 (v_i, v_{i+1}) が存在するものを選ぶ。そして、0 \leq i \leq 2K を満たす全ての i について辺 (v_i, v_{i+1}) を取り除く。

制約

  • 1 \leq N \leq 1.3 \times 10^5
  • 1 \leq K \leq 50
  • 入力される値は全て整数

入力

入力は以下の形式で標準入力から与えられる。

N K

出力

問題文の条件を満たす (2K + 1) N + 1 頂点の無向木 T の個数を 998244353 で割った余りを出力せよ。

入力例 1

2 1

出力例 1

8820

例えば辺 (1, 2), 辺 (2, 3), 辺 (2, 4), 辺 (2, 6), 辺 (3, 7), 辺 (4, 5) が存在する無向木を考えます。この木は以下の手順で操作を行うと全ての辺を取り除くことが出来るため、問題文の条件を満たします。

  • パス (1,2,4,5) を選ぶ。辺 (1,2), 辺 (2,4), 辺 (4,5) を取り除く。
  • パス (6,2,3,7) を選ぶ。辺 (6,2), 辺 (2,3), 辺 (3,7) を取り除く。

image

条件を満たす木は全部で 8820 個あります。

入力例 2

70 1

出力例 2

273892456

個数を 998244353 で割った余りを出力する点に注意してください。

入力例 3

12 29

出力例 3

898069699

入力例 4

100000 50

出力例 4

158600909

Score : 1800 points

Problem Statement

You are given positive integers N and K. Consider an undirected tree T with (2K + 1)N + 1 vertices labeled from 1 to (2K + 1)N + 1. Among all such trees, find the number, modulo 998244353, of trees that satisfy the following condition.

  • It is possible to remove all edges from T by repeating the following operation:
    • Choose a path of length 2K + 1 and remove all edges in it.
      Formally, choose a sequence of distinct vertices v_0, v_1, \dots, v_{2K+1} such that there exists an edge (v_i, v_{i+1}) for all i such that 0 \leq i \leq 2K, and remove the edge (v_i, v_{i+1}) for all i such that 0 \leq i \leq 2K.

Constraints

  • 1 \leq N \leq 1.3 \times 10^5
  • 1 \leq K \leq 50
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N K

Output

Print the number, modulo 998244353, of trees with (2K + 1)N + 1 vertices satisfying the condition.

Sample Input 1

2 1

Sample Output 1

8820

For example, consider a tree with edges (1, 2), (2, 3), (2, 4), (2, 6), (3, 7), and (4, 5). By doing the following steps, one can remove all edges from the tree, so it satisfies the condition in the problem statement:

  • Choose the path (1,2,4,5) and remove edges (1,2), (2,4), (4,5).
  • Choose the path (6,2,3,7) and remove edges (6,2), (2,3), (3,7).

image

There are 8820 such trees in total.

Sample Input 2

70 1

Sample Output 2

273892456

Remember to print the count modulo 998244353.

Sample Input 3

12 29

Sample Output 3

898069699

Sample Input 4

100000 50

Sample Output 4

158600909