這題我是按照官方解寫的，但官方解寫的蠻簡略的，這裡紀錄一下詳細作法。
我們要處理的問題現在已經轉換成要求「在一張二部圖中的所有有$t$條邊的匹配的權重總和」，其中一個匹配的權重等於裡面所有邊的邊權乘積。對每個$0\leq t\leq 50$都要求出這個東西的答案（要注意到空匹配的權重等於$1$）。我們可以把每個連通塊分開求，然後再合併成所求的答案陣列。具體來說，如果其中一個連通塊的答案陣列為$a$（也就是$a[0],...,a[50]$分別是那個連通塊的答案），另一個的則為$b$，那麼可以得到在這兩個連通塊中有$i$條邊的匹配的權重總和等於$\displaystyle \sum_{j=0}^{i} a[j]\cdot b[i-j]$，因為兩個連通塊中的邊數加起來要等於$i$。至於為什麼是直接相乘，因為$a[j]$其實是由好幾個$j$個數（邊權）的乘積加起來得到的，其中每個乘積都代表一種這個連通塊中的選$j$條邊的匹配方法，$b[i-j]$也類似，因此把這兩個數相乘就對應了「所有在第一塊中選$j$條，在第二塊中選$i-j$條的所有匹配的權重和」，恰好就是我們要的了。
因此現在就對每個連通塊分開處理，在第一種算法中，因為他是二部圖，設在這個連通分量中被分成的兩部份分別有$x,y$個點，那麼考慮$dp[i][j]$代表所有滿足以下條件的匹配的權重總和：這個匹配在第一部份中只用到了前$x$個點，並且在第二部份中有被匹配到的點的集合恰好為$j$。這樣的DP可以在$O(|E|\cdot 2^y)$的時間內找出所有的 DP 值，其中$|E|$是這個連通塊的邊數（DP的轉移式蠻顯然的，這裡省略），進而求出這個連通塊的答案。因此當$x$或$y\leq 17$時就可以使用這個算法。這裡要先處理好這個連通塊中的那$x$個點和$y$個點分別是誰，還有一個點是落在他那部份的第幾個點。
再來則是第二種算法，先找出這個連通塊的任意一個生成樹，把所有非樹邊都找出來，然後$2^k$暴力枚舉要用哪些非樹邊。所以這裡如果有一個點屬於被選到的兩條邊的話就是不合法的。選完之後算出共有幾條邊，還有這些邊的權重乘積，並且把被蓋到的點都標記起來，等一下不能夠選到有碰到這些點的邊。再來則是對這棵生成樹DP，因為我們需要的東西是「這棵樹中所有有$t$條邊的匹配的權重總和」，所以每個節點紀錄的東西就會是一個陣列，代表「在他以下的這棵子樹裡，所有有$t$條邊的匹配的權重總和」的對於每個$t$的答案。再來看如何轉移，因為在算$x$的DP陣列時，有一種可能是「取了$x$連到他其中一個兒子的這條邊當作匹配邊」，因此我們紀錄的狀態還要再多一維（只有$0$或$1$），代表那棵子樹的根是否有被匹配。這樣就可以轉移了，注意到這裡是要從$x$的子樹的DP陣列們合併成$x$本身的DP陣列，這可以一個子樹一個子樹合併，也就是當我們合併完前$i$棵子樹時，$x$本身的DP陣列會是「只考慮$x$的前$i$棵子樹，加上$x$這個點形成的子樹」的DP陣列。具體來說，記$dp[i][j][k]$代表滿足「以$i$為根的子樹中，選了$j$對匹配點，$k$代表是否有選到根（$k=0$代表沒有）」這些條件的匹配的權重總和，並且假設現在在算$x$的DP陣列，記$x_1,...,x_r$為所有$x$的子節點，那麼記$dp2[i][j][k]$代表「只看$x_1,...,x_i$這些子樹再加上$x$形成的子樹，裡面選了$j$對匹配點，$k$的意義一樣」的匹配的權重總和，那麼就不難列出轉移式了：
$dp2[i-1][j][0]\cdot (dp[x_i][j_2][0]+dp[x_i][j_2][1])$ 轉移到 $dp2[i][j+j_2][0]$
$dp2[i-1][j][1]\cdot (dp[x_i][j_2][0]+dp[x_i][j_2][1])$ 轉移到 $dp2[i][j+j_2][1]$
$dp2[i-1][j][0]\cdot dp[x_i][j_2][0]\cdot w_{x,x_i}$ 轉移到 $dp2[i][j+j_2+1][1]$
其中第三條轉移式只有在$x$和$x_i$都沒有被標記起來時才可以用，$w_{x,x_i}$代表$x$和$x_i$之間的這條邊的權重，邊界為$dp2[0][0][0]=1$。
如同許多需要在樹上合併DP陣列的題目一樣，因為每個節點的DP陣列大小都要開$k\cdot 2$，所以如果直接作的話單次DP複雜度會到$O(k^3)$，再乘上枚舉非樹邊的最差狀況$2^{17}$會TLE掉，而這只要注意到：對於一個子樹$x$來說，$dp[x][j][k]$在$2\cdot j>size[x]$時就都會是$0$了，因為沒有那麼多點可以匹配，其中$size[x]$是$x$的子樹的大小。因此當我們在從$dp2[i-1]$這個陣列去計算$dp2[i]$這個陣列時，令$S=x$的前$i-1$棵子樹的$size$總和$+1$，那麼我們只要用$dp2[i-1]$這個陣列的前$S/2+1$個值來轉移就好了（也就是$dp2[i-1][0][k],...,dp2[i-1][S/2][k]$），因為剩下的一定都是$0$。並且在枚舉$dp[x_i][j_2][k]$時$j_2$一樣枚舉到$size[x_i]/2$就夠了，後面的也都會是$0$。加了這件事之後單次DP複雜度就能降回$O(k^2)$了，證明可以參考這篇。大部份需要在樹上合併DP陣列的題目都可以用這件事來降複雜度。
code :
#include<bits/stdc++.h> #define pii pair<int,int> #define LL long long #define MOD 1000000007 using namespace std; const int maxn=200000+10,maxk=52 ; inline void add(LL &a,LL b){a=(a+b)%MOD ;} LL fac[maxn] ; struct P{int to,w;}; vector<P> v[maxn],v2[maxn] ; /// v2 : tree edge bool vis[maxn] ; int n,fa[maxn],in[maxn],out[maxn],tick ; int sz[maxn] ; int id[maxn],cnt1,cnt2,pt1[maxk],pt2[maxk] ; void dfs(int x,int f) { vis[x]=1 ; fa[x]=f ; sz[x]=1 ; in[x]=tick++ ; if(x<=n) pt1[cnt1]=x , id[x]=cnt1++ ; else pt2[cnt2]=x , id[x]=cnt2++ ; v2[x].clear() ; for(auto i : v[x]) if(!vis[i.to]) v2[x].push_back(i) , dfs(i.to,x) , sz[x]+=sz[i.to] ; out[x]=tick++ ; } inline bool isfa(int x,int y) /// x is fa of y { return in[x]<=in[y] && out[x]>=out[y] ; } LL dp0[2][1<<17] ; LL *solve0(int t) { memset(dp0,0,sizeof(dp0)) ; dp0[1][0]=1 ; int *pt=(!t ? pt1 : pt2) ; int cnt=(!t ? cnt1 : cnt2) , ma=cnt1+cnt2-cnt ; for(int i=0;i<cnt;i++) { fill(dp0[i%2],dp0[i%2]+(1<<17),0) ; for(int j=0;j<(1<<ma);j++) { add(dp0[i%2][j],dp0[(i+1)%2][j]) ; for(auto k : v[pt[i]]) if(j&(1<<id[k.to])) add(dp0[i%2][j],dp0[(i+1)%2][j^(1<<id[k.to])]*k.w) ; } } static LL ret[maxk] ; memset(ret,0,sizeof(ret)) ; for(int j=0;j<(1<<ma);j++) add(ret[__builtin_popcount(j)],dp0[(cnt-1)%2][j]) ; return ret ; } bool mark[maxn] ; LL dp[maxn][maxk][2],tmp[maxk][2] ; void DP(int x) { if(v2[x].empty()){dp[x][0][0]=1 ; dp[x][0][1]=0 ; return ;} for(auto i : v2[x]) DP(i.to) ; fill(dp[x][0],dp[x][sz[x]/2]+2,0) ; dp[x][0][0]=1 ; for(int i=0,sum=1;i<(int)v2[x].size();i++) { int xi=v2[x][i].to , w=v2[x][i].w , sz2=sz[xi] ; for(int j=0;2*j<=sum;j++) for(int k=0;k<2;k++) tmp[j][k]=dp[x][j][k] ; fill(dp[x][0],dp[x][(sum+sz2)/2]+2,0) ; for(int j=0;2*j<=sum;j++) for(int j2=0;2*j2<=sz2;j2++) { add(dp[x][j+j2][0],tmp[j][0]*(dp[xi][j2][0]+dp[xi][j2][1])) ; add(dp[x][j+j2][1],tmp[j][1]*(dp[xi][j2][0]+dp[xi][j2][1])) ; if(mark[x]||mark[xi]) continue ; add(dp[x][j+j2+1][1],(tmp[j][0]*dp[xi][j2][0]%MOD)*w) ; } sum+=sz2 ; } } struct E{int x,y,w;}; vector<E> edge ; /// not tree edge LL *solve1() { edge.clear() ; for(int i=0;i<cnt1;i++) for(auto j : v[pt1[i]]) if(j.to!=fa[pt1[i]] && fa[j.to]!=pt1[i] && isfa(j.to,pt1[i])) edge.push_back((E){pt1[i],j.to,j.w}) ; for(int i=0;i<cnt2;i++) for(auto j : v[pt2[i]]) if(j.to!=fa[pt2[i]] && fa[j.to]!=pt2[i] && isfa(j.to,pt2[i])) edge.push_back((E){pt2[i],j.to,j.w}) ; static LL ret[maxk] ; memset(ret,0,sizeof(ret)) ; int size=edge.size() ; for(int i=0;i<(1<<size);i++) { for(int j=0;j<cnt1;j++) mark[pt1[j]]=0 ; for(int j=0;j<cnt2;j++) mark[pt2[j]]=0 ; bool ok=1 ; LL mul=1LL ; int num=0 ; for(int j=0;j<size;j++) if(i&(1<<j)) { num++ ; if(mark[edge[j].x]||mark[edge[j].y]){ok=0 ; break ;} mark[edge[j].x]=mark[edge[j].y]=1 ; mul=mul*edge[j].w%MOD ; } if(!ok) continue ; int root=pt1[0] ; for(;root!=fa[root];root=fa[root]) ; DP(root) ; for(int j=0;2*j<=sz[root];j++) add(ret[num+j],(dp[root][j][0]+dp[root][j][1])*mul) ; } return ret ; } LL ans[maxk],tmp2[maxk] ; main() { int k ; scanf("%d%d",&n,&k) ; fac[0]=1 ; for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i%MOD ; while(k--) { int x,y,w ; scanf("%d%d%d",&x,&y,&w) ; v[x].push_back((P){n+y,w-1}) ; v[n+y].push_back((P){x,w-1}) ; } ans[0]=1 ; for(int i=1;i<=n;i++) if(!vis[i] && !v[i].empty()) { cnt1=cnt2=0 ; dfs(i,i) ; LL *ret ; if(cnt2<=17) ret=solve0(0) ; else if(cnt1<=17) ret=solve0(1) ; else ret=solve1() ; for(int j=0;j<maxk;j++) tmp2[j]=ans[j] , ans[j]=0 ; for(int j=0;j<maxk;j++) for(int j2=0;j+j2<maxk;j2++) add(ans[j+j2],tmp2[j]*ret[j2]) ; } LL ANS=0LL ; for(int i=0;i<maxk;i++) add(ANS,fac[n-i]*ans[i]) ; printf("%I64d\n",ANS) ; }
沒有留言:
張貼留言