33OJ
登录 注册

#P17619. [Math+Girl×1] Two Steps From Hell / Zero Sum Tree

    ID: 20215 远端评测题 1500ms 256MiB 尝试: 0 已通过: 0 显示难度NOI/NOI+/CTS 上传者: 标签>O2优化生成函数拉格朗日反演

[Math+Girl×1] Two Steps From Hell / Zero Sum Tree

背景

「人类认识这个宇宙的过程挺有趣的,不是吗?」

「他们一开始只是把一切无法理解之事归结为鬼神的影响;接着他们编造了许多种自以为是的学说;后来的实验推翻了那些说法,又创建了新的理论。他们总认为这个宇宙是简单的,而现在...」

「他们还在给粒子编号,给时间画刻度。他们以为只要足够耐心,就能把混沌也厘清。」

「但那是不可能的。他们每找到一条规律,就以为摸到了墙。其实那只是他们自己呼出的雾,凝在眼前。」

「你准备告诉他们吗?」

「不,他们不需要被告知。你也知道,他们会发现的。只是在某个寻常的清晨——」

「他们所珍视的一切规律与确定性将被尽数剥夺。」

题目描述

为了守护一丝规律,你决定解决如下问题并推广其做法:

对于有标号有根树 TT,设 v(T)v(T) 表示:将 TT 的每个节点 ii 赋权整数 xix_i,满足 −1≤xi≤k-1 \leq x_i \leq k,且任意子树内节点权值和非负,所有节点权值和为 00 的方案数。

对于所有 nn 个点的有标号有根树 TT,求 v(T)v(T) 之和,答案对 998244353998244353 取模。

输入格式

一行两个正整数 n,kn,k。

输出格式

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

4 1
460
50 5
727571900
59160 153
911492793

提示

本题开启捆绑测试。

::cute-table{tuack}

子任务 特殊限制 分数
11 n≤10n \leq 10 1010
22 n≤2000n \leq 2000 1515
33 n≤2×105n \leq 2\times10^5 3030
44 k=1k=1 1515
55 - 3030

对于所有数据,1≤n,k≤1071 \leq n,k \leq 10^7。