#P4752. 仙人掌计数

    ID: 3872 传统题 1000ms 128MiB 尝试: 32 已通过: 8 难度: 8 上传者: 标签>CF2500省选/NOI-仙人掌图指数生成函数导数积分转化卷积转化递推计数逆元线性递推鸣谢Tangjz提供试题

仙人掌计数

题目描述

定义仙人掌是一类无向图结构,而且在这种图上的边只会出现在至多一个环中。考虑有 nn 个点的仙人掌,点从 11 到 nn 标号,定义两个仙人掌是相同的,当且仅当它们对应的邻接矩阵完全相同。你的任务是统计 k=1,2,⋯ ,nk=1,2,\cdots,n 个点的带标号仙人掌有多少种,答案可能很大,你只需要给出答案对质数 pp 取模的值。

输入格式

仅一行,包含两个正整数 nn 和 pp,数字之间恰好有一个空格。

输出格式

输出 nn 行,第 ii 包含一个整数,表示 k=ik=i 时答案对 pp 取模的值。

4 23
1
1
4
8

数据规模与约定

对于 100%100\% 的数据,1≤n≤5001\le n\le500,n<p<230n<p<2^{30}。

题目来源

鸣谢 Tangjz 提供试题。