cf 512D - Fox And Travelling

题目大意

给定一颗\(n\le 100\)个点的图，可以进行随机游走，求游走\(k=0...n\)个点的方案数

游走的规则是：每次只能访问一个度数\(\le 1\)的点，并将其删除

分析

看完傻眼

问题1：随便顺序

问题2：稍微分析一下，发现环内的点不能选，甚至两个环的路径上的点都不能选

做法

对于问题2：并不需要缩点加奇怪处理找到不能选的点，只需要topu即可

可以发现，不可选集合会将联通快分成若干棵树，且不存在一棵树被不可选集合夹在中间的情况（这样的话这棵树就不可选，矛盾），于是划分出来的树一定所有节点的可选

整道题中，树有两类

1：有根树，即树根与一个不可选点相连，这时必须选完树中所有点才能选树根

2：无根树，即该联通快内不存在不可选点，此时哪个节点最后选择都可以

对于问题1：依然是树形背包dp

f[i][j]表示\(i\)子树中，选了\(j\)个点的方案数

dp合并的时候乘上组合数就好了

还是老问题：

\[\binom {a_1+a_2+..+a_n}{a_1~,~a_2~,~..~,~a_n}=\binom{a_1+a_2+..+a_n}{a_n}\cdots\binom{a_1+a_2}{a_2}\binom{a_1}{0}
\]

对于有根树是这样

那么对于无根树呢

我们枚举哪个节点最后删除，即对于树上每个点作为根求一次，dp值对应位加起来

此时对于\(n\)个点删除了\(i\)个点的情况，\(n-i\)个点作为根的时候都统计到了它，除一下

特别的，对于\(n\)个点删除了\(n\)个点的情况，不用除（也不能除n-n=0），因为这样既没有算重，也没有算漏，每个点最后删除的情况都枚举了，恰好就是所有情况

姿势

以后背包dp转移都可以写结构体，方便快捷

for循环边界思考过程：

枚举\(i+j=k\)的\(k\)，再枚举\(i\)

满足不等式\(0\le i\le n\),\(0\le k-i \le m\)

以及组合数注意C(x,y)时特判x<y否则越界

solution

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cmath>

#include <algorithm>

#include <vector>

using namespace std;

const int M=107;

const int N=1e4+7;

const int Q=1e9+9;

typedef long long LL;

inline int pls(int x,int y){return ((LL)x+y)%Q;}

inline int mns(int x,int y){return pls(x,Q-y);}

inline int mul(int x,int y){return 1LL*x*y%Q;}

inline int ri(){

	int x=0;bool f=1;char c=getchar();

	for(;!isdigit(c);c=getchar()) if(c=='-') f=0;

	for(;isdigit(c);c=getchar()) x=x*10+c-48;

	return f?x:-x;

}

int n,m;

int inv[M],fac[M],ifac[M];

int vis[M],ok[M],deg[M];

vector<int>pt;

inline int C(int x,int y){return (x>=y) ? mul(fac[x],mul(ifac[y],ifac[x-y])) : 0;}

void init(){

	int i;

	for(inv[1]=1,i=2;i<=n;i++) inv[i]=mul(inv[Q%i],Q-Q/i);

	for(fac[0]=1,i=1;i<=n;i++) fac[i]=mul(fac[i-1],i);

	for(ifac[0]=1,i=1;i<=n;i++) ifac[i]=mul(ifac[i-1],inv[i]);

}

struct vec{

	int g[M],te;

	struct edge{

		int y,nxt;

		edge(int _y=0,int _nxt=0){y=_y,nxt=_nxt;}

	}e[N<<1];

	vec(){memset(g,0,sizeof(g));te=1;}

	inline void push(int x,int y){e[++te]=edge(y,g[x]);g[x]=te;}

	inline void push2(int x,int y){push(x,y);push(y,x);}

	inline int& operator () (int x){return g[x];}

	inline edge& operator [] (int x){return e[x];}

}e;

struct node{

	int f[M],n;

	node(){n=0;memset(f,0,sizeof f);}

	void clear(){memset(f,0,sizeof f);n=0;}

	inline int& operator [] (int x){return f[x];}

	node operator *=(node &y){

		int i,j,tp;

		for(i=n+y.n;i>=0;i--){

			for(tp=0,j=max(i-n,0);j<=min(i,y.n);j++)

				tp=pls( tp, mul(C(i,j),mul(y[j],f[i-j])) );

			f[i]=tp;

		}

		n+=y.n;

	}

	node operator +=(node &y){

		int i;

		for(i=0;i<=y.n;i++) f[i]=pls(f[i],y[i]);

		n=max(n,y.n);

	}

}ans,sum,f[M];

void topu(){

	int i,h=0,t=0,x,p,y;

	static int q[M];

	for(i=1;i<=n;i++) if(deg[i]<=1) q[++t]=i;

	while(h!=t){

		x=q[++h];

		ok[x]=1;

		for(p=e(x);p;p=e[p].nxt){

			y=e[p].y;

			if(!ok[y]&&(--deg[y])<=1) q[++t]=y;

		}

	}

}

void dfs(int x,int fa){

	vis[x]=1;

	f[x].clear(); f[x][0]=1;

	int p,y;

	for(p=e(x);p;p=e[p].nxt)

	if((y=e[p].y)!=fa){

		dfs(y,x);

		f[x]*=f[y];

	}

	f[x].n++;

	f[x][f[x].n]=f[x][f[x].n-1];

}

void getpt(int x,int fa){

	pt.push_back(x);

	for(int p=e(x);p;p=e[p].nxt) if(e[p].y!=fa) getpt(e[p].y,x);

}

void gao(int x,int fa){

	if(fa!=0){

		dfs(x,fa);

		ans*=f[x];

	}

	else{

		int i,num;

		pt.clear(); getpt(x,0); sum.clear();

		for(i=0;i<pt.size();i++){

			dfs(pt[i],0);

			sum+=f[pt[i]];

		}

		for(i=0;i<pt.size();i++) sum[i]=mul(sum[i],inv[pt.size()-i]);

		ans*=sum;

	}

}

void solve(){

	int i,x,y;

	ans[0]=1;

	for(i=1;i<=m;i++){

		x=e[i<<1].y;

		y=e[i<<1^1].y;

		if(ok[x]!=ok[y])

			ok[x] ? gao(x,y) : gao(y,x);

	}

	for(i=1;i<=n;i++)

		if(ok[i]&&!vis[i]) gao(i,0);

}

int main(){

	int i,x,y;

	n=ri(),m=ri();

	for(i=1;i<=m;i++){

		x=ri(),y=ri();

		deg[x]++,deg[y]++;

		e.push2(x,y);

	}

	init();

	topu();

	solve();

	for(i=0;i<=n;i++) printf("%d\n",ans.f[i]);

	return 0;

}

巴特西

cf 512D - Fox And Travelling

题目大意

分析

做法

姿势

solution

最新文章

热门文章