[数学记录]AT2064 [AGC005F] Many Easy Problems
command_block
2021-01-12 10:43:57
**题意** : 给定一棵无根树。
定义 $f(k)$ 为 ：对所有大小为 $k$ 的点集，求能够包含它的最小连通块大小之和。
对于 $k=1\dots n$ 分别求出 $f(k)$。
答案对 $924844033=2^{21}*3^2*7^2+1$（质数） 取模。
$n\leq 2\times 10^5$ ，时限$\texttt{5s}$。
------------
妙妙题。
考虑点 $u$ 对 $f(k)$ 的贡献 ： 选出一个大小为 $k$ 的点集跨越 $u$ 的方案数。
对于 $u$ 而言，显然只需要考虑其各个分支的大小 $s_1,s_2,...,s_m$。
正着来有点不方便，考虑不跨越 $u$ 的方案数，那么必然只能完全在一个分支内。
不合法方案数为 $\sum\limits_{i=1}^m\dbinom{s_i}{k}$。总方案数为 $\dbinom{n}{k}$。
设 $c[s]$ 表示 $s$ 作为分支大小出现的次数，那么扣除的贡献即为 $\sum\limits_{i=1}^{n-1}c[s]\dbinom{s}{k}$。
这个拆开组合数随便卷一卷就是了。顺带一提，模数的原根是 $5$。
复杂度 $O(n\log n)$。
```cpp
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
#define pb push_back
#define ll long long
#define ull unsigned long long
#define MaxN 200500
#define Maxn 270500
using namespace std;
const int mod=924844033,_G=5;
ll powM(ll a,int t=mod-2){
ll ret=1;
while(t){
if (t&1)ret=ret*a%mod;
a=a*a%mod;t>>=1;
}return ret;
}
const int invG=powM(_G);
int tr[Maxn<<1];
void NTT(ll *g,bool op,int n)
{
static ull f[Maxn<<1],w[Maxn]={1};
for (int i=0;i<n;i++)f[i]=g[tr[i]];
for (int l=1;l<n;l<<=1){
ull tG=powM(op==1?_G:invG,(mod-1)/(l+l)),sav;
for (int i=1;i<l;i++)w[i]=w[i-1]*tG%mod;
for (int p=0;p<n;p+=(l+l))
for (int k=0;k<l;k++){
sav=w[k]*f[p|l|k]%mod;
f[p|l|k]=f[p|k]+mod-sav;
f[p|k]=f[p|k]+sav;
}
}if (op==0){
ll invn=powM(n);
for (int i=0;i<n;i++)
g[i]=f[i]%mod*invn%mod;
}else for (int i=0;i<n;i++)g[i]=f[i]%mod;
}
ll fac[MaxN],ifac[MaxN];
ll C(int n,int m)
{return fac[n]*ifac[m]%mod*ifac[n-m]%mod;}
void Init(int n)
{
fac[0]=1;
for (int i=1;i<=n;i++)
fac[i]=fac[i-1]*i%mod;
ifac[n]=powM(fac[n]);
for (int i=n;i;i--)
ifac[i-1]=ifac[i]*i%mod;
}
vector<int> g[MaxN];
int n,siz[MaxN];ll c[Maxn<<1],f[Maxn<<1];
void dfs(int u)
{
siz[u]=1;
for (int i=0,v;i<g[u].size();i++)
if (!siz[v=g[u][i]]){
dfs(v);
siz[u]+=siz[v];
c[siz[v]]++;
}
if (siz[u]<n)c[n-siz[u]]++;
}
int m;
int main()
{
scanf("%d",&n);Init(n);
for (int i=1,u,v;i<n;i++){
scanf("%d%d",&u,&v);
g[u].pb(v);g[v].pb(u);
}dfs(1);
int m=1;while(m<n+n)m<<=1;
for (int i=1;i<m;i++)
tr[i]=(tr[i>>1]>>1)|((i&1)?(m>>1):0);
for (int i=0;i<n;i++){
c[i]=c[i]*fac[i]%mod;
f[i]=ifac[i];
}reverse(c,c+n);
NTT(c,1,m);NTT(f,1,m);
for (int i=0;i<m;i++)c[i]=c[i]*f[i]%mod;
NTT(c,0,m);
reverse(c,c+n);c[n]=0;
for (int i=1;i<=n;i++)
printf("%lld\n",((C(n,i)*n-c[i]*ifac[i])%mod+mod)%mod);
return 0;
}
```