CF512D Fox And Travelling

第一篇博客

IOI2020集训队作业

首先我们考虑环中的点一定不会被遍历,然后我们就可以把环中点扔掉

紧接着我们有一些有根树和无根树,有根树就是树中唯一和环相连的,因为这样的点只能在在最后选

那么有根树上怎么树上背包呢?

f[i][j]+=f[x][j]*f[y][k]%P*(C(j+k,j))

相当于我们有个长度为j+k的序列向里面放一个长度为j的序列和一个长度为k的序列,肯定先硬点j个位置

无根树?枚举那个点做根然后有根树dp

最后不同的数背包+组合数合起来

注意无根树中一个j个点方案会被多算siz-j次

code:


#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=107;
const int P=1e9+9;
int n,m,d[MAXN],w[MAXN],b[MAXN],s[MAXN],S;
vector<int> e[MAXN];
ll p[MAXN],v[MAXN],vp[MAXN],f[MAXN][MAXN],ans[MAXN];

inline int read() {
	int x=0,f=1;
	char s=getchar();
	for(; !isdigit(s); s=getchar());
	for(; isdigit(s); s=getchar())x=(x<<1)+(x<<3)+s-'0';
	return x;
}

inline ll C(int a,int b) {
	return p[a]*vp[b]%P*vp[a-b]%P;
}

void dfs(int x,int o,int &s) {
	b[x]=o,++s;//拉出每个点所属的跟
	for(unsigned int i=0; i<e[x].size(); ++i) {
		int y=e[x][i];
		if(!d[y]&&!b[y])dfs(y,o,s);
	}
	return ;
}

inline void dp(int x,int fa) {
	s[x]=1,f[x][0]=1;
	for(unsigned int i=0; i<e[x].size(); ++i) {
		int y=e[x][i];
		if(b[x]!=b[y]||y==fa)continue;
		dp(y,x);
		for(int j=0; j<s[y]; ++j)f[x][s[x]+j]=0;
		for(int j=s[x]-1; ~j; --j) {//注意这里要减1
			for(int k=1; k<=s[y]; ++k) {
				f[x][j+k]=(f[x][j+k]+f[x][j]*f[y][k]%P*(C(j+k,j))%P)%P;
				//同一棵树上相当于dp了顺序
			}
		}
		s[x]+=s[y];//siz的意思
	}
	f[x][s[x]]=f[x][s[x]-1];//只能这么转移了
}

inline void get(int x) {
	dp(x,0);
	for(int i=0; i<=s[x]; ++i)f[0][i]=(f[0][i]+f[x][i])%P;
	//卷一下 
}

inline ll ksm(ll x,int y) {
	ll ans=1;
	while(y) {
		if(y&1)ans=ans*x%P;
		x=x*x%P;
		y>>=1;
	}
	return ans;
}

int main() {
	n=read();
	m=read();
	p[0]=v[0]=1;
	for(int i=1; i<=n; ++i)p[i]=p[i-1]*i%P;
	vp[n]=ksm(p[n],P-2);
	for(int i=n; i; --i)v[i]=p[i-1]*vp[i]%P,vp[i-1]=vp[i]*i%P;
//三种逆元?
//阶乘,逆阶乘逆元,单数
	for(int i=1,x,y; i<=m; ++i)x=read(),y=read(),e[x].push_back(y),e[y].push_back(x),++d[x],++d[y];
	queue<int> q;
	for(int i=1; i<=n; ++i)if(d[i]<=1)w[i]=1,q.push(i);
	//叶子结点!w是vis数组
	while(q.size()) {
		int x=q.front();
		q.pop();
		for(unsigned int i=0; i<e[x].size(); ++i) {
			int y=e[x][i];
			if(--d[y]<=1&&!w[y])w[y]=1,q.push(y);//当前的叶子节点
		}
	}
	for(int i=1; i<=n; ++i)
		if(d[i] == 1)dfs(i,i,s[i]);//从这些点出发dfs,统计大小和父亲
	for(int i=1; i<=n; ++i)if(!d[i]&&!b[i])dfs(i,i,s[i]);//我不联通的呢
	ans[0]=1;
	for(int i=1; i<=n; ++i)
		if(i==b[i]) {
			int o=s[i];
			if(d[i]==1)get(i);
			else {
				for(int j=1; j<=n; ++j)
					if(b[j]==i)get(j);//遍历这整棵树做根
				for(int j=0; j<=o; ++j)f[0][j]=f[0][j]*v[o-j]%P;
				//j个点的方案会被多算o-j次,因为在枚举o-j剩下的点做根的时候又会算一遍
			}
			for(int j=S; ~j; --j) {
				for(int k=1; k<=o; ++k) {
					ans[j+k]=(ans[j+k]+ans[j]*f[0][k]%P*C(j+k,j)%P)%P;//0一定要走了
				}
			}
			//这里背包一下
			for(int j=0; j<=o; ++j)f[0][j]=0;
			//清空一下
			S+=o;
		}
	for(int i=0; i<=n; ++i)printf("%d\n",ans[i]);
	return 0;
}

夏晓光(loveJY)的博客

博主所说