Fox And Travelling[CF512D]

发表于 分类于

题目链接

CF

题意

  • 给定一张 $n$ 个点 $m$ 条边的无向图。
  • 一个点只有当与它直接相连的点中最多只有一个点未被遍历过时才可被遍历。
  • 询问对于每个$k\in [0,n]$，遍历 $k$ 个点的方案数。
  • $n\leq 100$，对 $10^9+9$ 取模。

题解

首先来看看什么点是不能够被遍历的。

显然环中的点是不行的。两个环上点之间的路径上的点也是不行的。

可以发现，我们把整个图进行拓扑排序，有拓扑序的点就是能遍历的点。

那么把这些不能选的点去掉以后，剩下的是一堆树结构。这些树有两种情况：

  1. 有根树，即根节点的父亲是不能被遍历的。
  2. 无根树，即可以乱选的。

对于有根树我们直接进行树形背包DP，合并的时候乘一个组合数。

对于无根树，我们考虑沿用有根树的做法，对于每个点都来搞一次DP，然后将DP值相加。但发现会算重，对于一个选了 $k$ 个点的方案，那么在其他 $n-k$ 个点的DP中就会统计到它，因此最后将相加后的DP值除一个 $n-k$ 就好了。注意全选的时候是不用除的。

时间复杂度 $O(n^3)$。

程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
#include <bits/stdc++.h>
using namespace std;
#define FO(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define fo(i,j,k) for(int i=(j),end_i=(k);i<=end_i;i++)
#define ff(i,j,k) for(int i=(j),end_i=(k);i< end_i;i++)
#define fd(i,j,k) for(int i=(j),end_i=(k);i>=end_i;i--)
#define DEBUG(x) cerr<<#x<<"="<<x<<endl
#define all(x) (x).begin(),(x).end()
#define cle(x) memset(x,0,sizeof(x))
#define lowbit(x) ((x)&-(x))
#define ll long long
#define ull unsigned ll
#define db double
#define lb long db
#define pb push_back
#define mp make_pair
#define fi first
#define se second
inline int read()
{
	int x=0; char ch=getchar(); bool f=0;
	for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
	return f?-x:x;
}
#define CASET fo(___,1,read())
const int N=105;
const int M=20005;
ll fac[N],inv[N],ninv[N];
const ll mod=1e9+9;
inline ll Add(ll x,ll y){x+=y; return (x<mod)?x:x-mod;}
inline ll Dec(ll x,ll y){x-=y; return (x<0)?x+mod:x;}
inline ll Mul(ll x,ll y){return x*y%mod;}
inline ll Pow(ll x,ll y)
{
	y%=(mod-1);ll ans=1;for(;y;y>>=1,x=x*x%mod)if(y&1) ans=ans*x%mod;
	return ans;
}
#define Poly vector<ll>
inline Poly operator+(Poly A,Poly B)
{
	A.resize(max(A.size(),B.size()));
	ff(i,0,B.size()) A[i]=Add(A[i],B[i]);
	return A;
}
inline Poly operator*(Poly A,Poly B)
{
	int n=A.size()-1,m=B.size()-1;
	Poly C; C.resize(n+m+1);
	fo(j,0,n+m)
		fo(i,0,min(j,n))
			if(j-i<=m)
				C[j]=Add(C[j],A[i]*B[j-i]%mod*(fac[j]*inv[i]%mod*inv[j-i]%mod)%mod);
	return C;
}

inline void init(int n)
{
	fac[0]=1; fo(i,1,n) fac[i]=fac[i-1]*i%mod;
	inv[n]=Pow(fac[n],mod-2); fd(i,n,1) inv[i-1]=inv[i]*i%mod;
	ninv[1]=1;
	fo(i,2,n) ninv[i]=(mod-mod/i)*ninv[mod%i]%mod;
}
int n,m;
Poly ans,f[N],s;
int ver[M],ne[M],head[M],tot=1;
int deg[N];
bool flag[N],vis[N];
inline void add(int x,int y)
{
	ver[++tot]=y; ne[tot]=head[x]; head[x]=tot;
	ver[++tot]=x; ne[tot]=head[y]; head[y]=tot;
	deg[x]++; deg[y]++;
}
inline void topo()
{
	queue<int> q;
	fo(i,1,n) if(deg[i]<=1) q.push(i);
	for(int u,v;!q.empty();)
	{
		u=q.front(); q.pop(); flag[u]=1;
		for(int i=head[u];i;i=ne[i])
			if(!flag[v=ver[i]])
			{
				deg[v]--;
				if(deg[v]<=1) q.push(v);
			}
	}
}
void dfs(int u,int pre)
{
	vis[u]=1; f[u].clear(); f[u].pb(1);
	for(int i=head[u],v;i;i=ne[i])
		if((v=ver[i])!=pre)
			dfs(v,u),f[u]=f[u]*f[v];
	f[u].pb(0);
	f[u][f[u].size()-1]=f[u][f[u].size()-2];
}
vector<int> vec;
void dfs2(int u,int pre)
{
	vec.pb(u);
	for(int i=head[u],v;i;i=ne[i]) if((v=ver[i])!=pre) dfs2(v,u);
}

int main()
{
	n=read(); m=read();
	fo(i,1,m) add(read(),read());
	init(n);
	topo();
	int x,y;
	ans.pb(1);
	fo(i,1,m)
	{
		x=ver[i<<1],y=ver[i<<1|1];
		if(!flag[x]) swap(x,y);
		if(flag[x]&&!flag[y])
		{
			dfs(x,y);
			ans=ans*f[x];
		}
	}
	fo(i,1,n) if(flag[i]&&!vis[i])
	{
		vec.clear();
		dfs2(i,0);
		s.clear();
		for(auto u:vec)dfs(u,0),s=s+f[u];
		ff(i,0,vec.size()) s[i]=s[i]*ninv[vec.size()-i]%mod;
		ans=ans*s;
	}
	ans.resize(n+1);
	fo(i,0,n) printf("%d\n",ans[i]); 
	return 0;
}