CF512D. Fox And Travelling

题目大意

题解

首先只有能被拓扑的点才能被选，分成森林之后考虑计算

如果一个树的根仍连向未选点，那么这个根要选的话只能最后选，dp求

否则一个树没有固定的最后选的，直接算会算重，考虑对于一种方案将其唯一计算

把树提出来，把点按照拓扑序编号，每次硬点前i-1个必选，第i个必不选，这样就可以唯一算到，对于全选的方案以每个点为根都是不同的

code

#include <bits/stdc++.h>
#define fo(a,b,c) for (a=b; a<=c; a++)
#define fd(a,b,c) for (a=b; a>=c; a--)
#define C(n,m) (jc[n]*Jc[m]%1000000009*Jc[(n)-(m)]%1000000009)
#define add(a,b) a=((a)+(b))%1000000009
#define mod 1000000009
#define Mod 1000000007
#define ll long long
//#define file
using namespace std;

int a[101][101],c[101],D[101],d[101],size[101],n,m,i,j,k,l,x,y,h,t,tot,Tot;
ll jc[101],Jc[101],f[101][101],g[101],F[101][101];
bool bz[101],Bz[101],bz2[101],bz3[101],bz4[101];

ll qpower(ll a,int b) {ll ans=1; while (b) {if (b&1) ans=ans*a%mod;a=a*a%mod;b>>=1;} return ans;}

void work(int Fa,int t)
{
	int i,j,k,l;
	ll s=1;
	
	memset(f[t],0,sizeof(f[t]));
	size[t]=0,f[t][0]=1;
	fo(i,1,n)
	if (a[t][i] && bz[i] && i!=Fa)
	{
		memset(g,0,sizeof(g));
		fo(j,0,size[t])
		{
			fo(k,0,size[i])
			add(g[j+k],f[t][j]*f[i][k]%mod*C(j+k,k));
		}
		memcpy(f[t],g,sizeof(g));
		size[t]+=size[i];
		
		s=s*f[i][size[i]]%mod*C(size[t],size[i])%mod;
	}
	++size[t],add(f[t][size[t]],s);
	
	if (bz4[t])
	{fo(i,0,size[t]-1) f[t][i]=0;}
	else
	if (t==d[::j]) f[t][size[t]]=0;
}
void DFS(int Fa,int t)
{
	int i;
	bz2[t]=1;
	fo(i,1,n) if (a[t][i] && bz[i] && i!=Fa) DFS(t,i);
}
void Dfs(int Fa,int t)
{
	int i;
	
	fo(i,1,n)
	if (a[t][i] && bz[i] && i!=Fa)
	Dfs(t,i);
	work(Fa,t);
}

void dfs(int Fa,int t)
{
	int i;
	Bz[t]=1,bz3[t]=1;
	
	fo(i,1,n)
	if (bz[i] && a[t][i] && i!=Fa)
	dfs(t,i);
}

void Work(int t)
{
	int i,j,k,l;
	memset(g,0,sizeof(g));
	fo(j,0,tot)
	{
		fo(k,0,c[t])
		add(g[j+k],f[0][j]*F[t][k]%mod*C(j+k,k));
	}
	memcpy(f[0],g,sizeof(g)),tot+=c[t];
}

void WORK(int t)
{
	int i,j,k,l;
	Dfs(0,t),c[Tot]=size[t];
	fo(i,0,c[Tot]) add(F[Tot][i],f[t][i]);
}

int main()
{
	#ifdef file
	freopen("CF512D.in","r",stdin);
	#endif
	
	scanf("%d%d",&n,&m);
	fo(i,1,m) scanf("%d%d",&x,&y),a[x][y]=a[y][x]=1,++D[x],++D[y];
	jc[0]=Jc[0]=1;
	fo(i,1,n) jc[i]=jc[i-1]*i%mod;
	Jc[n]=qpower(jc[n],Mod);
	fd(i,n-1,1) Jc[i]=Jc[i+1]*(i+1)%mod;
	
	fo(i,1,n) if (D[i]<=1) d[++t]=i;
	while (h<t)
	{
		++h,bz[d[h]]=1;
		fo(i,1,n)
		if (a[d[h]][i])
		{
			--D[i];
			if (D[i]==1) d[++t]=i;
		}
	}
	
	fo(i,1,n) if (bz[i] && !bz2[i] && D[i]>0) DFS(0,i);
	Tot=0;
	fo(i,1,n)
	if (bz[i] && !Bz[i])
	{
		if (!bz2[i])
		{
			memset(bz3,0,sizeof(bz3));
			memset(bz4,0,sizeof(bz4));
			++Tot;
			dfs(0,i);
			
			fo(j,1,t)
			if (bz3[d[j]])
			WORK(d[j]),bz4[d[j]]=1;
			fo(j,1,t)
			if (bz3[d[j]])
			WORK(d[j]);
		}
		else
		if (D[i]>0)
		{
			++Tot,Dfs(0,i),c[Tot]=size[i];
			memcpy(F[Tot],f[i],sizeof(f[i]));
		}
	}
	f[0][0]=1;
	fo(i,1,Tot) Work(i);
	fo(i,0,n) printf("%lld
",f[0][i]);
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}