P12992 题解

dAniel_lele · 2025-10-26 23:27:19 · 题解

从大到小加边，做一个转化，k 个连通块相当于有 k 条边在加进来的时候两个点都没有任何连边。

考虑容斥，选定 i 条边加进来的时候两个点都没有任何连边，容斥及系数（选定 i 条边的方案数，注意不能有重复点）是平凡的，考虑如何计算确定这 i 条边后的概率。

首先给这 i 条边按大小定序。不妨把每条边视作一个点，选定的偏序关系视为有向边。于是我们将问题转化为了有向树拓扑序数量，套用经典结论概率即为 \prod\frac1{siz_j}。不难发现只有 i 个子树大小不为 1（即选定的 i 条边对应点的子树）。更进一步，我们会发现选定 i 对应的概率可以从 i-1 直接推，因此可以预处理出来做到 O(1) 计算。

总复杂度 O(TM)。

#include <bits/stdc++.h>
#define int long long
#define lowbit(i) (i&(-i))
using namespace std;
const int mod=1e9+7;
int qp(int a,int b){
    a%=mod;
    int ans=1;
    while(b){
        if(b&1) (ans*=a)%=mod;
        (a*=a)%=mod;
        b>>=1; 
    }
    return ans;
}
int fac[1000005],inv[1000005],invp[1000005],ipw[1000005];
void init(){
    ipw[0]=1; for(int i=1;i<=1000000;i++) ipw[i]=ipw[i-1]*((mod+1)>>1)%mod;
    fac[0]=1; for(int i=1;i<=1000000;i++) fac[i]=fac[i-1]*i%mod;
    inv[1000000]=qp(fac[1000000],mod-2); for(int i=999999;i>=0;i--) inv[i]=inv[i+1]*(i+1)%mod;
    for(int i=1;i<=1000000;i++) invp[i]=fac[i-1]*inv[i]%mod;
}
int C(int i,int j){
    if(i<0||j<0||i<j) return 0;
    return fac[i]*inv[j]%mod*inv[i-j]%mod;
}
int f[1000005];
void solve(int tc){
    int n,k; cin>>n>>k;
    f[0]=1;
    for(int i=1;(i<<1)<=n;i++) f[i]=f[i-1]*qp((i<<1)*(n-(i<<1))+i*((i<<1)-1),mod-2)%mod;
    int ans=0;
    for(int i=k;(i<<1)<=n;i++){
        if((i-k)&1) (ans+=mod-f[i]*C(i,k)%mod*fac[n]%mod*ipw[i]%mod*inv[n-(i<<1)]%mod)%=mod;
        else (ans+=f[i]*C(i,k)%mod*fac[n]%mod*ipw[i]%mod*inv[n-(i<<1)]%mod)%=mod;
    }
    cout<<"Case #"<<tc<<": "<<ans<<"\n";
}
signed main(){
    init();
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int t; cin>>t;
    for(int i=1;i<=t;i++) solve(i);
    return 0;
}