首页 > 其他分享 >P9663 Permutation on Tree 题解

P9663 Permutation on Tree 题解

时间:2024-02-08 20:15:29浏览次数:30  
标签:siz P9663 int 题解 Tree dfs MAXN 排布 mod

考虑枚举一个 \(x \in [1,n)\),将 \(\leq x\) 的看作 \(0\),\(>x\) 的看作 \(1\),那么一个排列的贡献实际上就是 \(\sum _{x=1}^{n-1}\sum [[p_i\leq x]+ [p_{i+1}>x]=1]\)。

那么问题转变为一个给定一棵树,每一个点有权值 \(0\) 或 \(1\),求所有排布方案的贡献之和。

设 \(f_x\) 表示 \(x\) 子树内的排布方案树之和是多少。

设 \(g_{x,k,0/1}\) 表示 \(x\) 子树内所有排布方案中第 \(k\) 个数是 \(0\) 还是 \(1\) 的排布方案有多少。

设 \(h_{x,k}\) 表示 \(x\) 子树内所有排布方案中第 \(k\) 个数和第 \(k+1\) 个数不同的方案数有多少。

在枚举一个 \(x\) 的情况时,贡献就是 \(\sum_{i=1}^{n-1} h_{r,i}\)。

转移方程建议自己手推。容易发现复杂度为 \(O(n^3)\)。

//code by Emissary
#include<bits/stdc++.h>

#define ll long long

using namespace std;

const int MAXN = 202;
const int mod = 1e9+7;

int n, r, siz[MAXN];
int val[MAXN], fac[MAXN<<1], ifac[MAXN<<1];
int head[MAXN], ne[MAXN<<1], to[MAXN<<1], cnt;
int f[MAXN], g[MAXN][MAXN][2], h[MAXN][MAXN], o[MAXN][MAXN][2], q[MAXN][MAXN];

inline void add(int x, int y){++cnt;to[cnt]=y;ne[cnt]=head[x];head[x]=cnt;}

inline int C(int x, int y){return x<y?0:1ll*fac[x]*ifac[y]%mod*ifac[x-y]%mod;}

inline ll Quickpow(ll x, ll y){
	ll z=1;
	while(y){
		if(y&1) z=z*x%mod;
		x=x*x%mod; y>>=1;
	}
	return z;
}

inline void dfs(int x, int fa){
	siz[x]=1; int lim;
	g[x][1][val[x]]=1; f[x]=1; 
	for(int i=head[x];i;i=ne[i]){
		if(to[i]==fa) continue;
		dfs(to[i],x);
		for(int j=0;j<=siz[x];++j) q[x][j]=h[x][j], h[x][j]=0;
		for(int j=2;j<=siz[x];++j)
			for(int k=1;k<=siz[to[i]];++k)
				(h[x][j+k-1]+=2ll*(1ll*g[to[i]][k][1]*g[x][j][0]%mod+1ll*g[to[i]][k][0]*g[x][j][1]%mod)%mod*C(j+k-3,j-2)%mod*C(siz[x]-j+siz[to[i]]-k,siz[x]-j)%mod)%=mod;
		(h[x][1]+=1ll*(1ll*g[to[i]][1][1]*g[x][1][0]%mod+1ll*g[to[i]][1][0]*g[x][1][1]%mod)*C(siz[x]-1+siz[to[i]]-1,siz[x]-1)%mod)%=mod;
		for(int j=2;j<siz[x];++j)
			for(int k=0;k<=siz[to[i]];++k)
				(h[x][j+k]+=1ll*q[x][j]*f[to[i]]%mod*C(j+k-2,k)%mod*C(siz[x]-j-1+siz[to[i]]-k,siz[to[i]]-k)%mod)%=mod;
		for(int k=1;k<siz[to[i]];++k)
			for(int j=1;j<=siz[x];++j)
				(h[x][j+k]+=1ll*h[to[i]][k]*f[x]%mod*C(j+k-2,j-1)%mod*C(siz[to[i]]-k-1+siz[x]-j,siz[x]-j)%mod)%=mod;	
		for(int j=0;j<=siz[x];++j) o[x][j][0]=g[x][j][0], o[x][j][1]=g[x][j][1], g[x][j][0]=g[x][j][1]=0;
		for(int j=2;j<=siz[x];++j){
			for(int k=0;k<=siz[to[i]];++k){
				(g[x][j+k][0]+=1ll*o[x][j][0]*f[to[i]]%mod*C(j+k-2,k)%mod*C(siz[x]-j+siz[to[i]]-k,siz[x]-j)%mod)%=mod;
				(g[x][j+k][1]+=1ll*o[x][j][1]*f[to[i]]%mod*C(j+k-2,k)%mod*C(siz[x]-j+siz[to[i]]-k,siz[x]-j)%mod)%=mod;
			}
		}
		for(int k=1;k<=siz[to[i]];++k){
			for(int j=1;j<=siz[x];++j){
				(g[x][j+k][0]+=1ll*g[to[i]][k][0]*f[x]%mod*C(j+k-2,j-1)%mod*C(siz[to[i]]-k+siz[x]-j,siz[x]-j)%mod)%=mod;
				(g[x][j+k][1]+=1ll*g[to[i]][k][1]*f[x]%mod*C(j+k-2,j-1)%mod*C(siz[to[i]]-k+siz[x]-j,siz[x]-j)%mod)%=mod;
			}
		}
		f[x]=1ll*f[x]*f[to[i]]%mod*C(siz[x]+siz[to[i]]-1,siz[to[i]])%mod; g[x][1][val[x]]=f[x]; 
		if(siz[x]>1) (h[x][1]+=1ll*q[x][1]*C(siz[x]+siz[to[i]]-2,siz[x]-2)%mod*f[to[i]]%mod)%=mod;
		siz[x]+=siz[to[i]];
	}
	return ;
}

inline void prework(int lim){
	fac[0]=ifac[0]=1;
	for(int i=1;i<=lim;++i) fac[i]=1ll*fac[i-1]*i%mod, ifac[i]=Quickpow(fac[i],mod-2);
	return ;
}

inline void clear(){
	memset(f,0,sizeof f);
	memset(g,0,sizeof g);
	memset(h,0,sizeof h);
	return ;
}

int main(){
	cin >> n >> r;
	prework(n<<1);
	for(int i=2;i<=n;++i){
		int x, y;
		cin >> x >> y;
		add(x,y), add(y,x);
	}
	int ans=0;
	for(int x=1;x<n;++x){
		for(int i=1;i<=n;++i) val[i]=(i>x);
		clear(); dfs(r,0);
		for(int i=1;i<n;++i) (ans+=h[r][i])%=mod;
	}
	cout << ans;
	return 0;
}

标签:siz,P9663,int,题解,Tree,dfs,MAXN,排布,mod
From: https://www.cnblogs.com/OccasionalDreamer/p/18012090

相关文章

  • P9697 Canvas 题解
    首先观察到有一个关键性质是\(1\leqx_i,y_i\leq2\)。那么我们贪心的考虑我们肯定会将\((x,y)=(1,1)\)的在一开始操作,\((x,y)=(2,2)\)的最后操作。也就是说现在没有固定的是\((x,y)=(1,2)\)和\((x,y)=(2,1)\)的。我们不妨令\((x,y)=(1,2)\),然后连边\((l,r)\)。然......
  • P10013 Tree Topological Order Counting 题解
    首先题目里面写了每一个数都有权值,一般这种题只能去想求出每一个的具体方案数,那么也就是我们得求出\(h_{i,j}\)表示在所有合法拓扑序中\(a_i=j\)的方案数。一颗树的拓扑序数量是\(\dfrac{n!}{\prodsiz_i}\),相信大家都知道。因为我们需要保证这一棵树满足拓扑排序的条件,不......
  • P10068 [CCO2023] Line Town 题解
    好题,但是感觉写起来有点屎。题目大意给定一个序列\(a\),你每次可以选择\(i\in[1,n-1]\),交换\(a_i,a_{i+1}\),并且给\(a_i,a_{i+1}\)取相反数。问你最少需要多少次交换才能使得序列非降,可能无解。做法首先考虑给偶数位置初始乘上\(-1\),然后操作变成交换相邻两个数,下面提......
  • CF1706E 题解
    你谷题目传送门CF题目传送门题目大意给定一个\(n\)个点\(m\)条边的无向图,询问\(q\)次,每次询问会指定两个正整数\(l,r\),问要使对于\(l\leqa\leqb\leqr\)的所有\(a,b\)均有路径可以互相到达,最少需要加入前多少条边。思路考虑到每一次询问实质上就是问你在按......
  • [COCI2007-2008#1] ZAPIS 题解
    题目传送门前置知识区间型动态规划思考过程这题也算是一道很经典的问题了(?)。看见\(n\leq200\),不难想到复杂度为\(O(n^3)\)的区间型动态规划。题面中有这么一段话。空串是规则括号序列。如果\(\textttA\)是规则括号序列,那么\(\texttt{(A)[A]{A}}\)都是规则括号......
  • CF1735D Meta-set 题解
    题目大意给定\(n\)张卡牌,每张卡牌有\(k\)个属性,第\(i\)张卡牌的第\(j\)个属性为\(c_{i,j}\)。一个由\(3\)张卡牌\(x,y,z\)组成的集合被称作好的,当且仅当对于\(1\leqi\leqk\)均有\(c_{x,i}=c_{y,i}=c_{z,i}\)或者\(c_{x,i},c_{y,i},c_{z,i}\)两两不相等。......
  • CF1793E Velepin and Marketing 题解
    题目大意有\(n\)个读者,第\(i\)年他们要一起读\(k_i\)本书,每一本书至少要让一个人读,每一个人也只能读恰好一本书。如果某一个人\(j\),如果有\(a_j\)个人这一年里和他读了同一本书,那么他就会感到满足。对于所有的\(q\)组询问,每组给定一个\(k_i\),求感到满足的人数的最......
  • CF1735E House Planning 题解
    题目大意一条直线上有\(n\)个房子和两个人,房子的坐标\(d_1,d_2,d_3\dotsd_n\),以及两个人坐标为\(p_1,p_2\)。现在会告诉你两个集合\(S_1=\{|p_1-d_i|,1\leqi\leqn\}\)以及\(S_2=\{|p_2-d_i|,1\leqi\leqn\}\)。这个写法可能不是很规范,但为了美观就写成这样了。......
  • CF1847E Triangle Platinum? 题解
    感谢@swiftc管理反馈的信息,对于题目大意确定的东西进行了完善。交互题。题目大意有一个长度为\(n\)的序列\(a\)满足\(1\leqa_i\leq4\),现在你可以进行不超过\(5500\)次询问,每次询问询问三个数\(1\leqi<j<k\leqn\),你将会得到\(a_i,a_j,a_k\)构成的三角形......
  • element-plus 2.4.1版本 el-tree踩坑
    element-plus2.4.1版本el-tree设置属性props中的label时,无法指定,例如<el-tree:data="datas.tree_data"show-checkboxnode-key="menu_id":props="{//label:function(data,node){//returndata.menu_name;//},......