题解：AT_agc060_c [AGC060C] Large Heap

思路

题面要求排列需要满足“堆”的性质，那我们不妨直接把它看成一个满足小根堆性质的满二叉树。

前置

如何求满足小根堆性质的满二叉树的个数呢？

排列的总个数为

n!

，而每个节点需要满足必须小于他子树的所有节点，则需要除以

sz[x]

。

那么总方案为

\dfrac{n!}{\prod_{i=1}^{n}sz[i]}

。

容易观察

u,v

两点分别在树的左链和右链上，与其他无关。所以我们单独把左右链提出来，用类似于归并排序的思路从小到大加点。

令

dp[i][j]

为左链跳到

i

且右链跳到

j

时

P_u<P_v

的概率。

首先排除不合法的情况，即

P_u > P_v

的情况，因为是从小到大加点：当右链已经跳到

v

，左链还没跳到

u

时。

接着考虑转移：

1.左链移动到

i+1

，则满足

P_{i+1} < P_{j+1}

，此时需要计算概率。

P_{i+1}

原本的子树个数为

2^{n-i}-1

，合并后因为

P_{i+1} < P_{j+1}

，子树个数要加上

j+1

的子树个数，为

2^{n-i}+2^{n-j}-2

。那么概率为

\dfrac{2^{n-i}-1}{2^{n-i}+2^{n-j}-2}

。

2.右链移动到

j+1

，则满足

P_{j+1} < P_{i+1}

，同理可得概率为

\dfrac{2^{n-j}-1}{2^{n-i}+2^{n-j}-2}

。

然后就做完了。

CPP

#include<bits/stdc++.h>
#define int long long
#define PII pair<int,int>
#define INF 1e12
#define cc cin
#define oo cout
#define nm tie(0)
using namespace std;
const int mod=998244353;
int qpow(int a,int b){
	int ans=1;
	while(b){
		if(b&1) ans=ans*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return ans;
}
int n,a,b;
int p[5005];
int dp[5005][5005];
signed main(){
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	ios::sync_with_stdio(false);
	cc.nm;
	oo.nm;
	cin>>n>>a>>b;
	a++,b++;
	p[0]=1;
	for(int i=1;i<=n;i++) p[i]=p[i-1]*2%mod;
	dp[1][1]=1;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(i<a&&j>=b) continue;
			dp[i+1][j]+=(dp[i][j]*(p[n-i]-1)%mod*qpow(p[n-i]+p[n-j]-2,mod-2)%mod);
			dp[i+1][j]%=mod;
			dp[i][j+1]+=(dp[i][j]*(p[n-j]-1)%mod*qpow(p[n-i]+p[n-j]-2,mod-2)%mod);
			dp[i][j+1]%=mod; 
		}
	}
	cout<<dp[n][n]<<"\n";
	return 0;
}
/*

*/

题解：AT_agc060_c [AGC060C] Large Heap

文章操作

思路

相关推荐

评论

题解：AT_agc060_c [AGC060C] Large Heap