题解：AT_agc060_c [AGC060C] Large Heap

one_last_kiss · 2025-10-17 20:12:10 · 题解

思路

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

::::info[前置]{open} 如何求满足小根堆性质的满二叉树的个数呢？

排列的总个数为 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}。

然后就做完了。

#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;
}
/*

*/