这是一道 模板题。
给定正整数 $ n,q,mod $。保证 $ mod $ 是质数。
对于一棵以点 $ 1 $ 为根的有根树 $ T $,设 $ s(T) $ 为这棵树中最多能选出多少个互不同构的子树(也就是这颗树本质不同的子树个数),那么这个树的权值 $ w(T) = q^{s(T)} $。
对于所有 $ 1 \le m \le n $,输出所有大小为 $ m $,根为 $ 1 $ 的有标号树的权值之和对 $ mod $ 取模后的值。
两棵有根树 $ T_1 $、$ T_2 $ 同构当且仅当他们的大小相等,且存在一个顶点排列 $ \sigma $ 使得在 $ T_1 $ 中 $ i $ 是 $ j $ 的祖先当且仅当在 $ T_2 $ 中 $ \sigma(i) $ 是 $ \sigma(j) $ 的祖先。
输入格式
一行两个整数,表示 $ n,q,mod $。
输出格式
输出 $ n $ 行,第 $ m $ 行表示 $ m $ 个点的答案。
样例输入 1
3 2 998244353
样例输出 1
2 4 20
样例解释 1
$ n=3,q=2,mod=998244353 $ 时,有三颗不同三个点的根为 $ 1 $ 的有标号树,其中两颗满足 $ w(T)=2^3 $,另一颗满足 $ w(T)=2^2 $。因此答案为 $ (2 \times 2^3+2^2) \bmod 998244353 = 20 $。
样例输入 2
11 4514 998244353
样例输出 2
4514 20376196 299712732 706663250 721357660 977589073 794002114 369586566 663682963 347458730 524354925
样例输入 3
40 787788 998244853
样例输出 3
787788 699879231 445785131 857102003 759492151 898159394 575712517 634469464 412999753 814233648 333451903 852329440 584109489 270769240 532457985 79235443 2228568 266810999 310877128 614605839 485785485 338520973 113751992 692026056 664258393 650448721 505881810 237159658 107178163 629910112 513627947 915509519 737809847 921731327 233492829 202989716 728903945 776060784 105388817 121481849
限制与约定
对于所有测试数据,保证 $ n = 100, 10^8 \le mod \le 1.01 \times 10^9, 1 \le q < mod $,且 $ mod $ 是质数。
本题共 $ 1 $ 个子任务,每个子任务 $ 100 $ 分。你在每个子任务中的得分为该子任务所有测试点的得分的最小值。
你必须按照输出格式输出 $ n $ 个数,但是你可以输出错误的答案。如果你输出了 $ c $ 个正确的答案,那么你获得的分数按照如下方式计算:
- 对于 $ 0 \le c \le 20 $,你的得分为 $ 2c $ 分;
- 对于 $ 21 \le c \le 60 $,你的得分为 $ c + 20 $ 分。
- 对于 $ 61 \le c \le 100 $,你的得分为 $ \lfloor \frac{c}{2}\rfloor + 50 $ 分。
时间限制:$ \texttt{4s} $。 空间限制:$ \texttt{2048MB} $。
你可以使用下面的代码来加速你的取模。
struct fastmod {
typedef unsigned long long u64;
typedef __uint128_t u128;
int m;
u64 b;
fastmod(int m) : m(m), b(((u128)1 << 64) / m) {}
int reduce(u64 a) {
u64 q = ((u128)a * b) >> 64;
int r = a - q * m;
return r < m ? r : r - m;
}
} z(2);
void solve() {
long long mod = 998244353, qwq = 1e9;
z = fastmod(mod);
cout << z.reduce(qwq) << ' ' << qwq % mod << '\n';
}