闲话
这才是真正的闲话
最后讲了一下求导和积分
但是感觉没几个人听
听了也没几个人会
——by crs_line
如果有不会的东西都可以来找我！
给solution引流
但是高数很多东西真的比较基础了
要学的也不多
求导 积分 多元函数 高重积分 级数 然后没了
某人在祂今天未公开的闲话里说我不放图 我也是放的
是四个可爱！虽然略微Badend
桜が泣いている
わたしたちの春は
紛い物、紛い物だから
どうせ知ってたんだろう
わたしあなたから逃げないよ
I'll just be forever a phantom.
杂题
对于所有点数为 \(n\) 的树，如果其满足对于所有 \(i\in [2,n]\)，与 \(i\) 相连的 \(j\) 中有且只有一个点 \(j\) 满足 \(j<i\) ，那么我们称其为好树。对于 \(1\sim n\) 每个点求出来有多少好树满足重心为 \(i\)。这里重心定义为删去这个点后形成的所有连通块大小均小于 \(\frac{n-1}2\)。
\(3\le n\le 2\times 10^5\) 且 \(n\) 为奇数（所以不存在树有多个重心的情况）
“有且只有一个点 \(j\) 满足 \(j<i\)”这个东西可以通过强制以 \(1\) 为根来生成树来避免判定。
于是我们对 \(i\) 需要求的就是 以 \(1\) 为根， \(i\) 的子树大小 \(\ge \frac {n+1}2\)，其余点的子树大小 \(< \frac {n+1}2\) 的树的数量。
先考虑第一个条件。
我们设 \(f_i\) 为 \(i\) 节点的子树大小 \(\ge\frac {n+1}2\) 的树的数量。
我们考虑子树中有 \(j\) 个点，然后选出除自己外的 \(j-1\) 个点一共 \(\binom{n-1}{j-1}\) 种可能；不在子树内的节点每个节点需要一个编号比他小的父亲，可能性是 \((n-j-1)!\) 的；第 \(i\) 个点需要一个父亲，可能性是 \((i-1)\) 的；在子树中的 \(j-1\) 个点，每个点需要一个父亲，可能性是 \((j-1)!\) 的。
令 \(m = \frac{n+1}2\)，于是
然后我们 \(O(1)\) 求出了 \(f_i\)。
然后求答案。设 \(g_i\) 为 \(i\) 点的答案，我们有
\[g_i = f_i - \frac{\sum_{j=i+1}^n g_j}{i} \]\(g_i\) 是 \(f_i\) 减去 \(i\) 子树内存在重心 \(j\) 情况的答案。\(j\) 是重心且在 \(i\) 子树内的可能性为 \(\frac 1i\) ，因此有转移式。
于是 \(O(n)\) 求解答案。
code :
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for (register int (i) = (a); (i) <= (b); ++(i))
#define pre(i,a,b) for (register int (i) = (a); (i) >= (b); --(i))
const int N = 2e5 + 10, mod = 998244353;
int jc[N<<1], inv[N<<1], n, m, f[N], ans[N], sum;
int qp(int a, int b) { int ret = 1; while (b) { if (b & 1) ret = 1ll * ret * a % mod; a = 1ll * a * a % mod; b >>= 1; } return ret; }
signed main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> n; m = (n + 1) / 2;
jc[0] = inv[0] = 1;
rep(i,1,n) jc[i] = 1ll * jc[i-1] * i % mod;
inv[n] = qp(jc[n], mod - 2);
pre(i,n-1,1) inv[i] = 1ll * inv[i+1] * (i+1) % mod;
pre(i,n-m+1,1) ans[i] = (1ll * jc[n-i] * jc[n-m] % mod * inv[n-i-m+1] % mod - 1ll * sum * qp(i, mod - 2) % mod + mod) % mod, sum = (sum + ans[i]) % mod;
rep(i,1,n) cout << ans[i] << ' ';
}