← 返回题目列表

AtCoder · agc070_e

E. 删除 2K+1 条边

中文机器翻译题面 查看原题

分数: 1800 点

问题陈述

给你正整数 N 和 K。考虑一棵无向树 T 与 (2K + 1)N + 1 顶点标记自 1 to (2K + 1)N + 1。在所有这样的树中,找到数字,模 998244353,满足以下条件的树。

  • 可以删除所有边缘 T 通过重复以下操作:
    • 选择长度的路径 2K + 1 并删除其中的所有边缘。
      正式地,选择一系列不同的顶点 v_0, v_1, \dots, v_{2K+1} 使得存在边缘 (v_i, v_{i+1}) 对于所有人 i 这样 0 \leq i \leq 2K,并删除边缘 (v_i, v_{i+1}) 对于所有人 i 这样 0 \leq i \leq 2K.

约束

  • 1 \leq N \leq 1.3 \times 10^5
  • 1 \leq K \leq 50
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N K

输出

打印数字,模数 998244353,树木 (2K + 1)N + 1 满足条件的顶点。


示例输入 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