锐客网

  1. 首页 > it技术 > >

DP|[矩阵树定理][prufer序][CF917D]Stranger Trees

dp计数类问题数论杂知识点图论杂题

题目描述
给定一棵n个点组成的有标号的树T，我们定义两棵有标号的树的相似度为它们共有的边的个数。
现在我们想知道，n个点的完全图所有的有标号的生成树中，有多少棵树与T的相似度为 0，1，2 … n - 1，答案对10^9+7取模
对于20%的数据，n <= 6。
对于40%的数据，n <= 15。
对于另外20%的数据，T中存在一个度数为n - 1的点。
对于100%的数据，2 <= n <= 100
解题思路
prufer 完全图，可以从prufer序角度考虑一下。
顺着暴力来：假如我们选出T的k条边，标记为必选，那么这个时候如果我们能快速知道此情况下生成树个数，那么就得到了相似度大于等于K的生成树的一些方案。统计所有情况，再容斥，就可以求出每一种相似度的答案了。
观察一下，此时联通块个数为n-k，设为m，若把联通块看成一个点，那么把联通块连起来的生成树的个数，由prufer序可知是 mm?2m m ? 2 个，然而一个联通块包含很多点，你在序列上填了一个联通块的编号，实际上可以是这个联通块里任意一个点，那么每个位置可以填1~n。另外，你不知道儿子联通块是哪个点连到父亲，最后剩下的两个联通块的边也没有确定时哪个点。那么方案数实际上是 nm?2?∏i=1..msize[i]n m ? 2 ? ∏ i = 1.. m s i z e [ i ] ，其中size[i]代表第i个联通块大小。
我们可以DP出对于每一个m，所有方案的 ∏i=1..msize[i]∏ i = 1.. m s i z e [ i ] 和。然后再乘上 nm?2n m ? 2 ，再容斥即可。注意到知道了联通块个数，就知道相似度了。
我们可以在T上树形DP，设f[i][j][k]表示i为根的子树，有j个联通块，其中i的联通块大小为k。那么对于一个x和他的儿子son，有两种转移。注意到i的联通块的k先不乘进去。
1,选择x-son的边， f‘[x][i+k?1][j+l]+=f[x][i][j]?f[son][k][l]f ‘ [ x ] [ i + k ? 1 ] [ j + l ] + = f [ x ] [ i ] [ j ] ? f [ s o n ] [ k ] [ l ]
2,不选, f′[x][i+k][j]+=f[x][i][j]?f[son][k][l]?lf ′ [ x ] [ i + k ] [ j ] + = f [ x ] [ i ] [ j ] ? f [ s o n ] [ k ] [ l ] ? l
最后的容斥就随便搞搞组合数就行了。
时间复杂度上界是 O(n4)O ( n 4 )
矩阵树定理 仍从暴力出发，在完全图中，我们枚举可能选的T的K条边，然后屏蔽掉剩下的T的边，在基尔霍夫矩阵上随便搞一个余子式，即可求出剩下的图的生成树个数。此时，求出的是相似度至多为K的方案。
考虑带权生成树计数的做法，此时我们的基尔霍夫矩阵不再是度数矩阵减邻接矩阵，而是边权和矩阵减去边权矩阵。这里一颗生成树的贡献是边权的乘积。
类似的，对于T的边，标记其为变量x。仍然对他求行列式，可以得出一个多项式，发现多项式i次项的系数，就是相似度为i时的生成树方案。
由于不能暴力求含未知数的行列式，我们带n个常数进去算，然后得出点值再拉格朗日插值回来，也可以算出答案。
时间复杂度严格 O(n4)O ( n 4 )
代码
【DP|[矩阵树定理][prufer序][CF917D]Stranger Trees】只有第一种做法的代码。

#include #include #include #include #include #include using namespace std; typedef long long ll; typedef double db; #define fo(i,j,k) for(i=j; i<=k; i++) #define fd(i,j,k) for(i=j; i>=k; i--) #define cmax(a,b) (a=(a>b)?a:b) #define cmin(a,b) (a=(a>=1; x=1ll*x*x%mo; } return ret; } void predo(int n) { fac[0]=1; fo(i,1,n) fac[i]=1ll*fac[i-1]*i%mo; rev[n]=ksm(fac[n],mo-2); fd(i,n,1) rev[i-1]=1ll*rev[i]*i%mo; } int c(int n,int m) { return 1ll*fac[m]*rev[n]%mo*rev[m-n]%mo; } void dfs(int x,int y) { f[x][1][1]=1; siz[x]=1; for(int p=fst[x]; p; p=nxt[p]) if (b[p]!=y) { dfs(b[p],x); fo(i,0,siz[x]+siz[b[p]]) fo(j,0,siz[x]+siz[b[p]]) g[i][j]=0; fo(i,1,siz[x]) fo(j,1,siz[x]-i+1) if (f[x][i][j]) fo(k,1,siz[b[p]]) fo(l,1,siz[b[p]]-k+1) if (f[b[p]][k][l]) { g[i+k-1][j+l]=(g[i+k-1][j+l]+1ll*f[x][i][j]*f[b[p]][k][l])%mo; g[i+k][j]=(g[i+k][j]+1ll*f[x][i][j]*f[b[p]][k][l]%mo*l)%mo; } siz[x]+=siz[b[p]]; fo(i,1,siz[x]) fo(j,1,siz[x]) f[x][i][j]=g[i][j]; } } int main() { freopen("c.in","r",stdin); freopen("c.out","w",stdout); scanf("%d",&n); predo(100); fo(i,1,n-1) { scanf("%d %d",&x,&y); cr(x,y); cr(y,x); } dfs(1,0); fo(i,1,n) { fo(j,1,n-i+1) prt[n-i]=(prt[n-i]+1ll*f[1][i][j]*j)%mo; prt[n-i]=1ll*prt[n-i]*ksm(n,i-2)%mo; } fd(i,n-1,0) fo(j,i+1,n-1) prt[i]=(prt[i]-1ll*prt[j]*c(i,j))%mo; fo(i,0,n-1) printf("%d ",(prt[i]+mo)%mo); }

    推荐阅读


    上一篇：并查集|[CF938G] Shortest Path Queries

    下一篇：思维题|Maze（CodeForces - 377A ）（思维，广搜）