#P7218. [2023省队模拟]最终对决

    ID: 7052 传统题 1000ms 512MiB 尝试: 2 已通过: 2 难度: 9 上传者: 标签>CF2700省选/NOI-双射计数计数 DPPascal 递推一维前缀和

[2023省队模拟]最终对决

题目描述

MOSS 先构造一棵包含 nn 个带编号顶点的树 SS,每个顶点的度都不超过 dd。

接下来 Bob 选择两个不同的顶点 x,yx,y(1≤x,y≤n1\le x,y\le n)。记从 xx 到 yy 的最短路径上依次经过的顶点编号为 T=(a1,a2,…,ak)T=(a_1,a_2,\ldots,a_k)。

最后,MOSS 选择一个整数 ii(1≤i≤k−11\le i\le k-1)和以下一种操作:

  1. 保留 a1,…,aia_1,\ldots,a_i,将后缀倒序后每项加上 aia_i。所得序列为 $a_1,\ldots,a_i,a_k+a_i,a_{k-1}+a_i,\ldots,a_{i+1}+a_i$。
  2. 保留 a1,…,aia_1,\ldots,a_i,将后缀的每一项 aja_j 替换为 ai−aja_i-a_j。所得序列为 $a_1,\ldots,a_i,a_i-a_{i+1},a_i-a_{i+2},\ldots,a_i-a_k$。

若操作后的序列严格单调(严格递增或严格递减),则 MOSS 获胜,否则 Bob 获胜。

双方都按最优策略行动。若存在多种必胜策略,可以任选其一。若必败,也可以任意决策。

求所有可能的最终局面 (S,x,y,i,opt)(S,x,y,i,opt) 的个数,其中 opt=1,2opt=1,2 分别表示选择第一种、第二种操作。答案对 998244353998244353 取模。

输入格式

一行两个整数 n,dn,d。

输出格式

输出一行一个整数,表示答案。

样例输入 1

2 1

样例输出 1

4

样例输入 2

5 3

样例输出 2

1720

数据范围与约定

对于所有数据,n≤500n\le500,1≤d≤n−11\le d\le n-1。大样例来自最终数据。

子任务 特殊限制 分值 依赖
1 n≤5n\le5 5 无
2 d=2d=2 15
3 d=n−1d=n-1
4 n≤20n\le20 20 1
5 n≤50n\le50 15 1、4
6 无特殊限制 30 1、2、3、4、5