php网站留言,建设学校网站的作用,5建网站,长春市建设集团股份有限公司CF512D Fox And Travelling 给定一张 \(n\) 个点 \(m\) 条边的无向图#xff0c;每次选择一个叶子结点并将它和连接它的边删除。 对于每个 \(k\in[0,n]\)#xff0c;问有序选择 \(k\) 个点的方案数。 \(n\le 100\)。 显然如果有环#xff0c;那么所有环上的点都无法被选择每次选择一个叶子结点并将它和连接它的边删除。 对于每个 \(k\in[0,n]\)问有序选择 \(k\) 个点的方案数。 \(n\le 100\)。 显然如果有环那么所有环上的点都无法被选择可以选择的只是一棵棵树。 按照是否有环可以将所有树分为两类求出每一棵树的答案再背包乘起来 一棵单独的树可以被取完从各个方向都可以选择直接背包计算即可。树根连在“环”上只可以从儿子向上取。 \(\color{yellow}{\bigstar\texttt{Trick}}\)按照上面的方法将每个点当做根节点做一遍。设树的大小为 \(n\)发现每种选择 \(k\) 个点的情况都会在 \(n-k\) 个点中计算一遍那么答案除 \(n-k\) 即可。 将长度为 \(l_1,l_2\) 的序列合并起来的方案数为 \(\binom{l_1l_2}{l_1}\)那么直接用背包合并即可。 #define Maxn 105
#define Maxm 10005
#define mod 1000000009
int n,m,tot,cnt;
int C[Maxn][Maxn],ind[Maxn];
int hea[Maxn],nex[Maxm1],ver[Maxm1];
bool Covered[Maxn];
vectorint g[Maxn];
inline void add(int x,int y){ ver[tot]y,nex[tot]hea[x],hea[x]tot; }
inline ll ksm(ll x,ll ymod-2)
{ll ret1;for(;y;y1,xx*x%mod) if(y1) retret*x%mod;return ret;
}
struct TREE
{int opt,rt,sall,siz[Maxn];ll dp[Maxn],tmp[Maxn][Maxn];void dfs(int x,int fa){tmp[x][0]1,siz[x]0;for(int v:g[x]) if(v!fa){dfs(v,x);for(int susiz[x];su0;su--) for(int sv1;svsiz[v];sv)(tmp[x][susv]tmp[x][su]*tmp[v][sv]%mod*C[susv][sv]%mod)%mod;siz[x]siz[v];}(tmp[x][siz[x]1]tmp[x][siz[x]])%mod;siz[x];}inline void ADD(int x){memset(tmp,0,sizeof(tmp)),dfs(x,0);for(int i0;isall;i) (dp[i]tmp[x][i])%mod;}void Find(int x,int fa) { ADD(x); for(int v:g[x]) if(v!fa) Find(v,x); }void Count(int x,int fa) { sall; for(int v:g[x]) if(v!fa) Count(v,x); }void solve(){Count(rt,0);if(opt0) { Find(rt,0); for(int i0;isall;i) dp[i]dp[i]*ksm(sall-i)%mod; }else ADD(rt);}
}subtree[Maxn];
ll ans[Maxn];
int main()
{C[0][0]1;for(int i1;i100;i){C[i][0]1;for(int j1;ji;j) C[i][j](C[i-1][j]C[i-1][j-1])%mod;}nrd(),mrd();for(int i1,u,v;im;i)urd(),vrd(),add(u,v),add(v,u),ind[u],ind[v];queueint q;for(int i1;in;i) if(ind[i]1) q.push(i);while(!q.empty()){int curq.front(); q.pop();bool existfalse;Covered[cur]true;for(int ihea[cur];i;inex[i]){if(Covered[ver[i]]) g[cur].pb(ver[i]),g[ver[i]].pb(cur);else{existtrue,ind[ver[i]]--;if(ind[ver[i]]1) q.push(ver[i]);}}if(!exist) cnt,subtree[cnt].opt0,subtree[cnt].rtcur;}for(int i1;in;i) if(!Covered[i])for(int jhea[i];j;jnex[j]) if(Covered[ver[j]])cnt,subtree[cnt].opt1,subtree[cnt].rtver[j];for(int i1;icnt;i) subtree[i].solve();ans[0]1;for(int i1,pre0;icnt;i){for(int supre;su0;su--) for(int sv1;svsubtree[i].sall;sv)(ans[susv]ans[su]*subtree[i].dp[sv]%mod*C[susv][su]%mod)%mod;presubtree[i].sall;}for(int i0;in;i) printf(%lld\n,ans[i]);return 0;
}
