#P12577. [集训队互测 2024day14]Since A Light

    ID: 11739 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 10 上传者: 标签>CF3300组合数学动态规划FFT矩阵多项式计数DP倍增

[集训队互测 2024day14]Since A Light

题目背景

若音乐再响起

带领你我飞翔

我不会坠落

我会用尽所有力量

再一次手牵着手握紧让全世界共鸣

让我们再相遇

感受到你的梦想

题目描述

洛天依给了你一棵树,树初始只有一个根节点。 在时刻 00 到 n−1n-1,每个时刻会发生一次以下的操作:

  • 所有深度与当前时刻 tt 模 22 同余的点长出一个叶子。(根节点深度为 00,儿子节点的深度为父亲节点的深度 +1+1)。

求 nn 次操作后树上距离为 dd 的无序点对的数量,对 998244353998244353 取模。

输入格式

一行两个整数 n,dn,d,分别表示操作次数和距离。

输出格式

一行一个整数 ansans,表示无序点对数模 998244353998244353 后的结果。

样例

输入 #1

5 3

输出 #1

16

样例解释

img

无序点对分别为 (1,5)(1,5),(1,10)(1,10),(1,11)(1,11),(1,12)(1,12),(2,7)(2,7),(2,8)(2,8),(3,4)(3,4),(3,9)(3,9),(3,11)(3,11),(3,13)(3,13),(4,6)(4,6),(5,6)(5,6),(6,7)(6,7),(6,10)(6,10),(7,9)(7,9),(8,10)(8,10),一共 1616 个。

数据范围

对于所有数据:1≤n≤1091\leq n\leq 10^9,1≤d≤1051\leq d\leq 10^5。

SubtaskSubtask 1 (1 pts)1\ (1 \ pts) :1≤n≤251\leq n\leq 25,1≤d≤4001\leq d\leq 400。

SubtaskSubtask 2 (7 pts)2\ (7 \ pts) :1≤n≤4001\leq n\leq 400,1≤d≤4001\leq d\leq 400。

SubtaskSubtask 3 (10 pts)3\ (10 \ pts) :1≤n≤20001\leq n\leq 2000,1≤d≤20001\leq d\leq 2000。

SubtaskSubtask 4 (14 pts)4\ (14 \ pts) :1≤n≤50001\leq n\leq 5000,1≤d≤50001\leq d\leq 5000。

SubtaskSubtask 5 (19 pts)5\ (19 \ pts) :1≤d≤1001\leq d\leq 100。

SubtaskSubtask 6 (36 pts)6\ (36 \ pts) :1≤d≤50001\leq d\leq 5000。

SubtaskSubtask 7 (13 pts)7\ (13 \ pts) :无特殊限制。