Exber's Blog

Can't go up

【2022 NOIP 模拟赛 28】构树 做题记录

发布于 2023-04-08 | 标签: DP 、 组合计数 、 做题记录 、 数学 | 12分钟 | 1973字数

奆 ζ\zeta 有一颗 nn 个点有标号的树，点从 1∼n1\sim n 标号，边从 1∼n−11\sim n-1 标号为 ui,vi(i<n)u_i,v_i(i\lt n)。

现在他想在这棵树的基础上构造一些新的树

具体的，他想知道在能构造出的所有 nn 个点有标号无根树中，恰好的有 xx 条边与原树相同的数量

并且对于每个 x∈[0,n−1]∩Zx\in[0,n-1]\cap \mathbb{Z}，输出答案 mod⁡109+7\operatorname{mod} 10^9+7 的结果。

原题：CF917D Stranger Trees

首先若求出 f(i)f(i) 表示钦定 ii 条边固定的方案数，设 ans(i)ans(i) 为恰好 ii 条边相同的方案数，显然有：

ans(i)=∑j=in−1(−1)j−i(ji)f(j)ans(i)=\sum\limits_{j=i}^{n-1}(-1)^{j-i}\binom{j}{i}f(j)

考虑求出 f(i)f(i)，钦定了 ii 条边固定就相当于有 n−in-i 个连通块，有个结论：

有 mm 个点，每个点有 aia_i 种连边方式的树有 (∑ai)m−2∏ai(\sum a_i)^{m-2}\prod a_i。

证明：

考虑生成出来的树的长度为 m−2m-2 的 prufer 序列，显然每个位置可以任选。ii 的度即为它在 prufer 序列中出现的次数 +1+1，所以每个点的贡献是 ai出现次数+1a_i^{\text{出现次数}+1}，把 +1+1 拉出来，变成 (∏ai出现次数)(∏ai)(\prod a_i^{\text{出现次数}})(\prod a_i)。

所有情况下的 ∏ai出现次数\prod a_i^{\text{出现次数}} 之和显然和 (∑ai)m−2(\sum a_i)^{m-2} 是等价的，得证。

那么考虑设 dpu,i,jdp_{u,i,j} 表示 uu 的子树，选了 ii 条边，包含 uu 的连通块大小为 jj 的 ∑∏siz\sum\prod siz（jj 没有乘进去）。

dpu,i,j=∑k=0i∑l=1jdpu,i−k−1,j−l×dpv,k,l+∑k=0i−1∑ldpu,i−k,j×l×dpv,k,ldp_{u,i,j}=\sum\limits_{k=0}^i\sum\limits_{l=1}^j dp_{u,i-k-1,j-l}\times dp_{v,k,l}+\sum\limits_{k=0}^{i-1}\sum\limits_l dp_{u,i-k,j}\times l\times dp_{v,k,l}

考虑优化，压掉一维，设 fu,i=∑jdpu,i,j,gu,i=∑jj×dpu,i,jf_{u,i}=\sum\limits_{j}dp_{u,i,j},g_{u,i}=\sum\limits_{j}j\times dp_{u,i,j}，考虑转移，有：

fu,i=∑jdpu,i,j=∑j∑k=0i−1∑l=1jdpu,i−k−1,j−l×dpv,k,l+∑j∑k=0i∑ldpu,i−k,j×l×dpv,k,l=∑k=0i−1fu,i−k−1×fv,k+∑k=0ifu,i−k×gv,k\begin{aligned} f_{u,i}&=\sum\limits_{j}dp_{u,i,j}\\ &=\sum\limits_{j}\sum\limits_{k=0}^{i-1}\sum\limits_{l=1}^j dp_{u,i-k-1,j-l}\times dp_{v,k,l}+\sum\limits_{j}\sum\limits_{k=0}^i\sum\limits_l dp_{u,i-k,j}\times l\times dp_{v,k,l}\\ &=\sum\limits_{k=0}^{i-1} f_{u,i-k-1}\times f_{v,k}+\sum\limits_{k=0}^{i}f_{u,i-k}\times g_{v,k} \end{aligned}

gu,i=∑jj×dpu,i,j=∑jj∑k=0i−1∑l=1jdpu,i−k−1,j−l×dpv,k,l+∑jj∑k=0i∑ldpu,i−k,j×l×dpv,k,l=∑j∑k=0i−1∑l=1j(j−l+l)×dpu,i−k−1,j−l×dpv,k,l+∑k=0igu,i−k×gv,k=∑j∑k=0i−1∑l=1j(j−l)×dpu,i−k−1,j−l×dpv,k,l+∑j∑k=0i−1∑l=1jl×dpu,i−k−1,j−l×dpv,k,l+∑k=0igu,i−k−1×gv,k=∑k=0i−1gu,i−k−1×fv,k+∑k=0i−1fu,i−k−1×gv,k+∑k=0igu,i−k×gv,k=∑k=0i−1gu,i−k−1×fv,k+fu,i−k−1×gv,k+∑k=0igu,i−k×gv,k\begin{aligned} g_{u,i}&=\sum\limits_{j}j\times dp_{u,i,j}\\ &=\sum\limits_{j}j\sum\limits_{k=0}^{i-1}\sum\limits_{l=1}^j dp_{u,i-k-1,j-l}\times dp_{v,k,l}+\sum\limits_{j}j\sum\limits_{k=0}^{i}\sum\limits_l dp_{u,i-k,j}\times l\times dp_{v,k,l}\\ &=\sum\limits_{j}\sum\limits_{k=0}^{i-1}\sum\limits_{l=1}^j (j-l+l)\times dp_{u,i-k-1,j-l}\times dp_{v,k,l}+\sum\limits_{k=0}^{i}g_{u,i-k}\times g_{v,k}\\ &=\sum\limits_{j}\sum\limits_{k=0}^{i-1}\sum\limits_{l=1}^j (j-l)\times dp_{u,i-k-1,j-l}\times dp_{v,k,l}+\sum\limits_{j}\sum\limits_{k=0}^{i-1}\sum\limits_{l=1}^j l\times dp_{u,i-k-1,j-l}\times dp_{v,k,l}+\sum\limits_{k=0}^{i}g_{u,i-k-1}\times g_{v,k}\\ &=\sum\limits_{k=0}^{i-1}g_{u,i-k-1}\times f_{v,k}+\sum\limits_{k=0}^{i-1}f_{u,i-k-1}\times g_{v,k}+\sum\limits_{k=0}^{i}g_{u,i-k}\times g_{v,k}\\ &=\sum\limits_{k=0}^{i-1}g_{u,i-k-1}\times f_{v,k}+f_{u,i-k-1}\times g_{v,k}+\sum\limits_{k=0}^{i}g_{u,i-k}\times g_{v,k} \end{aligned}

代码如下：

// Problem: #148. 构树
// Contest: Hydro
// URL: http://oiclass.com/d/tigao/p/148
// Memory Limit: 256 MB
// Time Limit: 4000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

#define fio(name) freopen(name".in","r",stdin),freopen(name".out","w",stdout);

const int MS=8005,S=100005,p=1000000007;

int n;
int esum,to[S],nxt[S],h[MS];
int siz[MS];
vector<int> f[MS],g[MS];
int tmpf[MS],tmpg[MS];
int ml[MS],fra[MS],inv[MS];
int ans[MS];

inline void add(int x,int y)
{
	to[++esum]=y;
	nxt[esum]=h[x];
	h[x]=esum;
}

inline void addd(int &x,int y)
{
	x+=y;
	if(x>=p) x-=p;
}

inline int qpow(int x,int y)
{
	int res=1;
	for(;y>0;y>>=1,x=1ll*x*x%p) res=(y&1)?1ll*res*x%p:res;
	return res;
}

inline int C(int n,int m)
{
	return 1ll*fra[n]*inv[n-m]%p*inv[m]%p;
}

void dfs(int u,int fa)
{
	siz[u]=1;
	f[u].push_back(1),g[u].push_back(1);
	for(int i=h[u];i;i=nxt[i])
	{
		int v=to[i];
		if(v==fa) continue;
		dfs(v,u);
		for(int j=0;j<=n;j++) tmpf[j]=tmpg[j]=0;
		for(int j=0;j<=siz[u]-1;j++)
		{
			for(int k=0;k<=siz[v]-1;k++)
			{
				addd(tmpf[j+k+1],1ll*f[u][j]*f[v][k]%p);
				addd(tmpf[j+k],1ll*f[u][j]*g[v][k]%p);
				addd(tmpg[j+k+1],(1ll*g[u][j]*f[v][k]+1ll*f[u][j]*g[v][k])%p);
				addd(tmpg[j+k],1ll*g[u][j]*g[v][k]%p);
			}
		}
		siz[u]+=siz[v];
		for(int j=0;j<=siz[u]-1;j++)
		{
			if(j<f[u].size()) f[u][j]=tmpf[j],g[u][j]=tmpg[j];
			else f[u].push_back(tmpf[j]),g[u].push_back(tmpg[j]);
		}
	}
}

int main()
{
	fio("tree");
	scanf("%d",&n);
	for(int i=1;i<=n-1;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		add(x,y),add(y,x);
	}
	dfs(1,0);
	ml[0]=1;
	for(int i=1;i<=n;i++) ml[i]=1ll*ml[i-1]*n%p;
	fra[0]=1;
	for(int i=1;i<=n;i++) fra[i]=1ll*fra[i-1]*i%p;
	inv[n]=qpow(fra[n],p-2);
	for(int i=n;i>=1;i--) inv[i-1]=1ll*inv[i]*i%p;
	for(int i=0;i<=n-1;i++) ans[i]=i!=n-1?1ll*ml[n-i-2]*g[1][i]%p:1;
	for(int i=0;i<=n-1;i++)
	{
		int pre=0;
		for(int j=i;j<=n-1;j++)
		{
			if(j-i&1^1) addd(pre,1ll*C(j,i)*ans[j]%p);
			else addd(pre,p-1ll*C(j,i)*ans[j]%p);
		}
		printf("%d ",pre);
	}
	printf("\n");
	return 0;
}
# DP # 组合计数 # 做题记录 # 数学
已运行:
浏览数: 次 | 访客数: 人
Powered by Gridea
0%