#P12321. [蓝桥杯 2024 国研究生组] 生成树问题
[蓝桥杯 2024 国研究生组] 生成树问题
题目描述
给定 个点,编号 至 ,任意两点 之间均有且仅有一条边。如果 为完全平方数(也即存在整数 满足 ),那么其边权为 ,否则为 。
小蓝想要得到一棵生成树,其除 以外的每个点都有一个编号小于自己的点与其相邻。求小蓝想得到的所有生成树中,边权和为 至 的分别各有多少种,请输出答案对 取模的结果。
输入格式
输入一行包含一个整数 。
输出格式
输出 行,每行包含一个整数,依次表示边权和为 的生成树种数。
4
4
2
0
0
提示
评测用例规模与约定
- 对于 的评测用例,;
- 对于 的评测用例,;
对于所有评测用例,。