[集训队互测 2023] 树哈希

这是一道 [模板题](https://uoj.ac/problem/763)。 给定正整数 $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)$ 的祖先。 ## Input 一行两个整数，表示 $n,q,mod$。 ## Output 输出 $n$ 行，第 $m$ 行表示 $m$ 个点的答案。 [samples] ## Note #### 样例解释 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$。 #### 限制与约定 对于所有测试数据，保证 $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}$。 你可以使用下面的代码来加速你的取模。 ```cpp 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'; } ```