CF1667E Centroid Probabilities

题目描述

对于所有点数为 $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$ 为奇数（所以不存在树有多个重心的情况）

题解

设$m=\frac{n+1}{2}$，$f_i$表示$i$的子树大小$\ge m$的方案数
枚举$i$的子树大小$j$，则有式子
$$f_i=(i-1)\sum _{j=m}^{n-i+1}\left(\genfrac{}{}{0ex}{}{n-i}{j-1}\right)(j-1)!(n-j-1)!$$
前面的$i-1$是钦定$i$的父亲，组合数是从$i$后面的点中选出属于$i$子树的点，两个阶乘是为了计算两个点集连成树的方案数
$$=(i-1)\sum _{j=m}^{n-i+1}\frac{(n-i)!}{(j-1)!(n-i-j+1)!}(j-1)!(n-j-1)!$$

$$=(i-1)(n-i)!\sum _{j=m}^{n-i+1}\frac{(n-j-1)!}{(n-i-j+1)!}$$

$$=(n-i)!(i-1)!\sum _{j=m}^{n-i+1}\frac{(n-j-1)!}{(n-i-j+1)!(i-2)!}$$

$$=(n-i)!(i-1)!\sum _{j=m}^{n-i+1}\left(\genfrac{}{}{0ex}{}{n-j-1}{i-2}\right)$$

$$=(n-i)!(i-1)!\sum _{k=i-2}^{n-m-1}\left(\genfrac{}{}{0ex}{}{k}{i-2}\right)$$

$$=(n-i)!(i-1)!\left(\genfrac{}{}{0ex}{}{n-m}{i-1}\right)$$

于是$f_i$可以$O(n)$计算，考虑容斥求出$an{s}_i$表示以$i$为重心的方案数，枚举它的儿子$j$子树大小$\ge m$，显然对于$j$来说父亲为哪个方案数都是一样的，所以以$i$为父亲的方案数就是$\frac{f_j}{j-1}$，即答案为$an{s}_i=f_i-{\sum }_{j=i+1}\frac{f_j}{j-1}$

$\text{code}$

#include<cstdio>
#define ll long long
using namespace std;
const ll mod=998244353;
ll ksm(ll a,ll b)
{if(b==0) return 1;ll tmp=ksm(a,b>>1);if(b&1) return tmp*tmp%mod*a%mod;else return tmp*tmp%mod;
}
const int N=2e5+1000;
int n;
ll f[N+10],fac[N+10],inv[N+10];
ll C(int n,int m){if(m>n) return 0;return fac[n]*inv[m]%mod*inv[n-m]%mod;}
int main()
{scanf("%d",&n);fac[0]=inv[0]=1;for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i%mod,inv[i]=ksm(fac[i],mod-2);f[1]=fac[n-1];int m=n+1>>1;for(int i=2;i<=n;i++) f[i]=fac[i-1]*fac[n-i]%mod*C(n-m,i-1)%mod;ll res=0;for(int i=n;i>=1;i--){ll tmp=f[i];f[i]=(f[i]+mod-res)%mod;res+=tmp*ksm(i-1,mod-2)%mod,res%=mod;}for(int i=1;i<=n;i++) printf("%lld ",f[i]);puts("");return 0;
}