#P12321. [蓝桥杯 2024 国研究生组] 生成树问题

    ID: 13960 远端评测题 1500ms 512MiB 尝试: 0 已通过: 0 难度: 6 上传者: 标签>2024快速傅里叶变换 FFT蓝桥杯国赛

[蓝桥杯 2024 国研究生组] 生成树问题

题目描述

给定 nn 个点,编号 11nn,任意两点 x,yx, y 之间均有且仅有一条边。如果 xyx \cdot y 为完全平方数(也即存在整数 zz 满足 z2=xyz^2 = x \cdot y),那么其边权为 11,否则为 00

小蓝想要得到一棵生成树,其除 11 以外的每个点都有一个编号小于自己的点与其相邻。求小蓝想得到的所有生成树中,边权和为 00n1n-1 的分别各有多少种,请输出答案对 998244353998244353 取模的结果。

输入格式

输入一行包含一个整数 nn

输出格式

输出 nn 行,每行包含一个整数,依次表示边权和为 0n10 \sim n-1 的生成树种数。

4
4
2
0
0

提示

评测用例规模与约定

  • 对于 60%60\% 的评测用例,n5000n \leq 5000
  • 对于 85%85\% 的评测用例,n105n \leq 10^5

对于所有评测用例,1n3×1051 \leq n \leq 3 \times 10^5