4596: [Shoi2016]黑暗前的幻想鄉(xiāng)

Time Limit:?20 Sec??Memory Limit:?256 MB
Submit:?257??Solved:?152
[Submit][Status][Discuss]

Description

四年一度的幻想鄉(xiāng)大選開(kāi)始了，最近幻想鄉(xiāng)最大的問(wèn)題是很多來(lái)歷不明的妖 怪涌入了幻想鄉(xiāng)，擾亂了幻想鄉(xiāng)昔日的秩序。但是幻想鄉(xiāng)的建制派妖怪（人類） 博麗靈夢(mèng)和八云紫等人整日高談所有妖怪平等，幻想鄉(xiāng)多元化等等，對(duì)于幻想鄉(xiāng) 目前面臨的種種大問(wèn)題卻給不出合適的解決方案。 風(fēng)間幽香是幻想鄉(xiāng)里少有的意識(shí)到了問(wèn)題的嚴(yán)重性的大妖怪。她這次勇敢的 站了出來(lái)參加幻想鄉(xiāng)大選。提出包括在幻想鄉(xiāng)邊境建墻（并讓人類出錢），大力 開(kāi)展基礎(chǔ)設(shè)施建設(shè)挽回失業(yè)率等一系列方案，成為了大選年出人意料的黑馬并順 利的當(dāng)上了幻想鄉(xiāng)的大統(tǒng)領(lǐng)。 幽香上臺(tái)以后，第一項(xiàng)措施就是要修建幻想鄉(xiāng)的公路。幻想鄉(xiāng)有 N 個(gè)城市， 之間原來(lái)沒(méi)有任何路。幽香向選民承諾要減稅，所以她打算只修 N- 1 條路將 這些城市連接起來(lái)。但是幻想鄉(xiāng)有正好 N- 1 個(gè)建筑公司，每個(gè)建筑公司都想 在修路的過(guò)程中獲得一些好處。 雖然這些建筑公司在選舉前沒(méi)有給幽香錢，幽香還是打算和他們搞好關(guān)系， 因?yàn)樗€指望他們幫她建墻。所以她打算讓每個(gè)建筑公司都負(fù)責(zé)一條路來(lái)修。 每個(gè)建筑公司都告訴了幽香自己有能力負(fù)責(zé)修建的路是哪些城市之間的。所 以幽香打算選擇 N-1 條能夠連接幻想鄉(xiāng)所有城市的邊，然后每條邊都交給一 個(gè)能夠負(fù)責(zé)該邊的建筑公司修建，并且每個(gè)建筑公司都恰好修一條邊。 幽香現(xiàn)在想要知道一共有多少種可能的方案呢？兩個(gè)方案不同當(dāng)且僅當(dāng)它 們要么修的邊的集合不同，要么邊的分配方式不同。

?

Input

第一行包含一個(gè)正整數(shù) N(N<=17)， 表示城市個(gè)數(shù)。 接下來(lái) N-1 行，其中第 i行表示第 i個(gè)建筑公司可以修建的路的列表： 以一個(gè)非負(fù)數(shù)mi 開(kāi)頭，表示其可以修建 mi 條路，接下來(lái)有mi 對(duì)數(shù)， 每對(duì)數(shù)表示一條邊的兩個(gè)端點(diǎn)。其中不會(huì)出現(xiàn)重復(fù)的邊，也不會(huì)出現(xiàn)自環(huán)。

?

Output

僅一行一個(gè)整數(shù)，表示所有可能的方案數(shù)對(duì) 10^9 + 7 取模的結(jié)果。

?

Sample Input

4
2 3 2 4 2
5 2 1 3 1 3 2 4 1 4 3
4 2 1 3 2 4 1 4 2

Sample Output

17 詳細(xì)地講一下 不要問(wèn)為什么，這道題用容斥原理+矩陣樹(shù)定理 1.矩陣樹(shù)定理可以求一個(gè)單位權(quán)圖的生成樹(shù)的個(gè)數(shù)，這個(gè)東西可以自己上網(wǎng)找一下。 2.容斥原理： 首先我們想一下，題目要求每個(gè)公司選一條自己能建的邊，那么很好啊，我們把每個(gè)人的邊都加進(jìn)去，跑矩陣樹(shù)定理，不就出來(lái)了嗎？當(dāng)然不了，因?yàn)榭赡艹霈F(xiàn)某個(gè)人的邊沒(méi)被選。這很討厭，那么我們就要減去這些情況，這些情況都包含什么情況呢？假如一號(hào)公司的邊沒(méi)被選中，那么這些情況是要減掉的，不如我們把一號(hào)公司的邊全刪掉，再跑矩陣樹(shù)定理，加上，然后把二號(hào)公司的邊都刪去，然后。。。是不是就刪去了所有那些有人沒(méi)選的情況？不，這樣刪多了，因?yàn)槲覀內(nèi)サ粢惶?hào)公司的邊，跑矩陣樹(shù)定理，也把二號(hào)公司沒(méi)選的方案減了，跑二號(hào)公司時(shí)，這些情況也減去了，就減多了，那么怎么加上這些情況呢？不如我們把一號(hào)公司二號(hào)公司的邊全刪掉，再跑。。。一直這樣，這就是容斥原理。。。 2^n枚舉一個(gè)狀態(tài)，一個(gè)位是一表示這個(gè)公司的所有邊都加進(jìn)去了，如果公司%2的數(shù)量和總數(shù)%2相等，就加上，否則減去。 記住數(shù)組要開(kāi)大，邊數(shù)有17*16/2種。 #include<bits/stdc++.h> using namespace std; typedef long long ll; #define N 30 #define mod 1000000007 struct edge {int u[1010],v[1010],size; }x[N]; int n; ll ans; ll a[N][N],d[N][N],g[N][N]; ll gauss() {ll f=1,ret=1;for(int i=1;i<=n;++i){for(int j=i+1;j<=n;++j){ll A=g[i][i],B=g[j][i];while(B){ll t=A/B; A%=B; swap(A,B);for(int k=i;k<=n;++k) g[i][k]=((g[i][k]-t*g[j][k]%mod)%mod+mod)%mod;for(int k=i;k<=n;++k) swap(g[i][k],g[j][k]);f=-f;}} if(!a[i][i]) return 0;}for(int i=1;i<=n;++i) ret=ret*g[i][i]%mod;ret=(ret*f%mod+mod)%mod;return ret; } void solve() {for(int i=1;i<1<<n;++i){memset(a,0,sizeof(a));memset(g,0,sizeof(g));memset(d,0,sizeof(d));int tot=0;for(int j=1;j<=n;++j) if(i&(1<<(j-1))){++tot;for(int k=1;k<=x[j].size;++k){ int u=x[j].u[k],v=x[j].v[k];a[u][u]++; a[v][v]++;d[u][v]++; d[v][u]++;}}for(int j=1;j<=n;++j)for(int k=1;k<=n;++k) g[j][k]=a[j][k]-d[j][k];if(n%2==tot%2) ans+=gauss();else ans-=gauss();ans=(ans%mod+mod)%mod;}ans=(ans%mod+mod)%mod;printf("%lld\n",ans); } int main() {scanf("%d",&n);--n;for(int i=1;i<=n;++i){scanf("%d",&x[i].size);for(int j=1;j<=x[i].size;++j) scanf("%d%d",&x[i].u[j],&x[i].v[j]);} // if(!n) // { // puts("1"); // return 0; // } solve();return 0; } View Code

?

轉(zhuǎn)載于:https://www.cnblogs.com/19992147orz/p/6410981.html

總結(jié)

以上是生活随笔為你收集整理的bzoj 4596的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。