题解：P12992 [GCJ 2022 #1C] Intranets

· · 题解

简化题意

> 从所有 $\deg_u=0\lor\deg_v=0$ 的点对 $(u,v)$ 中等概率选一个，加边 $(u,v)$。 无法进行操作时停止。给定 $m$，求恰好 $m$ 次操作后停止的概率，答案对给定质数 $P$ 取模。这里的 $n,m$ 对应原题的 $M,M-K$。 ## $n\le 5

暴搜即可。

:::info[code]

//by lovely Autumn_Rain
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define For(i,l,r) for(int i=l;i<=r;i++)
int n,m,P;
vector<int>deg;
ll ans=0;
ll qpow(ll a,ll b){
    ll res=1;
    while(b){
        if(b&1)res=res*a%P;
        a=a*a%P;b>>=1;
    }
    return res;
}
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
void dfs(int cnt,vector<int>&deg,ll res){
    bool f=0;
    For(i,1,n)if(deg[i]==0){f=1;break;}
    if(!f){
        if(cnt==m)ans=(ans+res)%P;
        return;
    }
    vector<pii>G;
    ll num=0;
    For(u,1,n-1){
        For(v,u+1,n){
            if(!deg[u]||!deg[v]){
                G.pb(mp(u,v));
                num++;
            }
        }
    }
    if(num==0)return;
    ll inv=qpow(num,P-2)%P;
    for(pii &x:G){
        int u=x.fi,v=x.se;
        deg[u]++;deg[v]++;
        dfs(cnt+1,deg,res*inv%P);
        deg[u]--;deg[v]--;
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>m>>P;
    deg.resize(n+1,0);
    dfs(0,deg,1);
    cout<<ans%P;
    return 0;
}

:::

n\le 4\times 10^3

考虑 O(n^2) 动态规划。f_{i,j} 表示操作 i 次，现在还有 j 个孤立点的概率。

f_{i+1,j-2}=\binom{j}{2}f_{i,j} f_{i+1,j-1}=j\times(n-j)\times f_{i,j}

:::info[code]

//by lovely Autumn_Rain
#include<bits/stdc++.h> 
using namespace std; 
#define ll long long 
#define For(i,l,r) for(int i=l;i<=r;i++) 
int n,m;
ll P;
const int N=4e3+10;
ll f[N][N];
ll qpow(ll a,ll b){
    ll res=1;
    while(b){
        if(b&1)res=res*a%P;
        a=a*a%P;
        b>>=1;
    }
    return res;
}
int main(){ 
    ios::sync_with_stdio(0); 
    cin.tie(0);cout.tie(0); 
    cin>>n>>m>>P;
    f[0][n]=1;
    For(i,0,m-1){
        for(int j=n;j>=1;j--){
            if(f[i][j]==0)continue;
            ll t=(n*(n-1)/2-(n-j)*(n-j-1)/2+P)%P;
            ll inv=qpow(t,P-2)%P;
            if(j>=2)f[i+1][j-2]=(f[i+1][j-2]+j*(j-1)/2*inv%P*f[i][j]%P+P)%P;
            if(j>=1)f[i+1][j-1]=(f[i+1][j-1]+j*(n-j)*inv%P*f[i][j]%P+P)%P;
        }
    }
    cout<<(f[m][0]+P)%P;
    return 0; 
}

:::

m=n-1

打表或者推式子，答案为 \frac{2^{n-2}}{Catalan_{n-1}}。

:::info[code]

//by lovely Autumn_Rain
#include<bits/stdc++.h> 
using namespace std; 
#define ll long long 
#define For(i,l,r) for(int i=l;i<=r;i++) 
int n,m;
ll P;
const int N=4e3+10;
ll f[N][N];
ll qpow(ll a,ll b){
    ll res=1;
    while(b){
        if(b&1)res=res*a%P;
        a=a*a%P;
        b>>=1;
    }
    return res;
}
ll cal(int x){
    ll inv=qpow(x+1,P-2)%P;
    ll res=1;
    For(i,x+1,2*x){
        res=res*i%P;
        int ar=i-x;
        ll t=qpow(ar,P-2)%P;
        res=res*t%P;
    }
    return res*inv%P;
}
void solve(){
    ll res=cal(n-1);
    ll inv=qpow(res,P-2)%P;
    cout<<qpow(2,n-2)*inv%P;
}
int main(){ 
    ios::sync_with_stdio(0); 
    cin.tie(0);cout.tie(0); 
    cin>>n>>m>>P;
    if(m==n-1){solve();return 0;}
    f[0][n]=1;
    For(i,0,m-1){
        for(int j=n;j>=1;j--){
            if(f[i][j]==0)continue;
            ll t=(n*(n-1)/2-(n-j)*(n-j-1)/2+P)%P;
            ll inv=qpow(t,P-2)%P;
            if(j>=2)f[i+1][j-2]=(f[i+1][j-2]+j*(j-1)/2*inv%P*f[i][j]%P+P)%P;
            if(j>=1)f[i+1][j-1]=(f[i+1][j-1]+j*(n-j)*inv%P*f[i][j]%P+P)%P;
        }
    }
    cout<<(f[m][0]+P)%P;
    return 0; 
}

:::

O(n) 正解

两种操作情况。

假设做了 c_0 次操作一，c_1 次操作二，那么有：

$\ \ \ \ c_0+2\times c_1=n$。 $\therefore c_1=n-m$。 不妨假设 $k=n-m$，那么 $k$ 就是操作二的数目。 总共有 $\binom{n}{2}$ 条边，这些边任意顺序操作共 $\binom{n}{2}!$ 种情况。我们考虑在所有情况里筛选符合题意的排列。每次操作到不合法的情况就操作跳过（可以发现这并不影响概率）。 此时可以进行操作二，要求两个点先前没有连过边，也就是不存在先前就已经操作完的相邻边。 我们希望刚好选出 $k$ 条这样的操作二边。 这个问题太难了，考虑至少选出 $k$ 条操作二边怎么做，也就是选 $x\geq k$ 条出来。如果解决了这个问题，就可以容斥一下 $k$ 的贡献，最终得出刚好 $=k$ 条操作二边的答案。具体的容斥系数是 $(-1)^{x-k}\binom{x}{k}$。 把合法的边排序改写成依赖关系，有向边 $e_i\rightarrow e_j$ 代表先访问 $i$ 再访问 $j$。 此时的排列方案数相当于一个 DAG 的拓扑序个数。要求这 $x\geq k$ 条边比相邻的边要更早选择。我们先人为钦定一下这 $x$ 条边的顺序（最后再乘上排列数 $\binom{n}{2x}(2x-1)!!$ 就可以了）。 :::success[为什么是 $(2x-1)!!$] 我们选出了 $2x$ 个点，两两配对连边的过程如下： - 点 1 可以和另外 $2x-1$ 个点配。 此时配完剩下 $2x-2$ 个点。 - 点 2 可以和另外 $2x-3$ 个点配。 此时配完剩下 $2x-4$ 个点。 - …… 最终结果 $(2x-1)\times(2x-3)\times \cdots =(2x-1)!!$。 ::: 现在相当于，有 $\binom{n}{2}$ 条边，已经钦定下来边集 $(0,1),(2,3)\cdots(2x-2,2x-1)$。对于剩下的 $\binom{n}{2}-x$ 条边都执行操作 1。 因此这些边和钦定边一定相邻，且比相邻钦定边遍历的晚（如果当前边先于相邻钦定边遍历，就会导致操作钦定边时某端点度数不为 $0$，矛盾了）。 因此，如果该边某端点在钦定边上，那么它在树上的父亲就是它相邻的钦定边中编号最靠前的一个。否则，就连到 $(2x-2,2x-1)$ 这条边上。 :::warning[一个形象的小剧场] $x$ 个领导（边）排好了队，你是个牛马。 如果同时被多个领导赏识，就跟在最靠排位前的领导后面干。 如果没有人赏识，就跟着排名最差的那个老板干。 ::: 这样连出来会是一颗树，因为每个边只有一个父亲，要么跟着编号靠前的边走，要么连到最后面。答案就是这颗树的拓扑序个数。 $n$ 个点的树的拓扑序个数： $$n!\times \prod_{i=1}^{n}\frac{1}{sz_i}$$ 我们发现按照上面那种连接方法是可以算出每个子树的 $sz$ 的。非钦定边都是叶子结点，可以不用考虑。与 $(2x-2,2x-1)$ 相邻的边有 $2n-4$ 条。与 $(2x-4,2x-3)$ 相邻且不与 $(2x-2,2x-1)$ 相邻的边有 $2n-8$ 条…… 因此钦定点的 $sz_i=1+\sum_{j\le i}(2n-4j)$。 :::success[推导过程] 以最后一条钦定边 $(2x-2,2x-1)$ 为例： 它占了 $2$ 个点，剩下 $n-2$ 个孤立点。每个孤立点都能和这条钦定边的 $2$ 个端点各连一条非钦定边。 所以非钦定边数量 $2\times(n-2)=2n-4$ 条，这些边都只粘在这条钦定边上。 --- 再看倒数第二条钦定边 $(2x-4,2x-3)$： 它自己占 $2$ 个点，前面最后一条钦定边已经占了 $2$ 个点，剩下 $n-4$ 个孤立点。 所以数量 $2×(n-4)=2n-8$ 条，同样只粘在这条钦定边上。 以此类推，第 $j$ 条钦定边对应的非钦定边数量就是 $2n-4j$ 条。 --- 为什么 $sz_i=1+\sum_{j\le i}(2n-4j)$？ $sz_i$ 是子树里边的总数。子树里包括它自己 $1$ 条钦定边，还有所有依赖它的非钦定边。 倒数 $i$ 条边都是这个子树里的，所以把粘在它们上面的边分别加起来即可。 ::: 拓扑序个数： $$\binom{n}{2}!\times \prod_{i=1}^{x}\frac{1}{i+\sum_{j=1}^{i}(2n-4j)}$$ $$\binom{n}{2}!\times\prod_{i=1}^{x}\frac{1}{(-2i^2+2ni-i)}$$ $$\binom{n}{2}!\times\frac{1}{x!}\prod_{i=1}^{x}\frac{1}{(-2i+2n-1)}$$ $$\binom{n}{2}!\times\frac{(2n-3-2x)!!}{x!(2n-3)!!}$$ 因为求的是概率，所以去掉了全情况 $\binom{n}{2}!$，答案是： $$\frac{(2n-3-2x)!!}{x!(2n-3)!!}$$ 因为一开始钦定 $x$ 条边一个顺序。总共有 $x!$ 种顺序，每种顺序的答案都是这个，所以最终答案里分母的 $x!$ 抵掉了。 算上容斥和顺序数，最终结果： $$\sum_{x=k}^{\left \lfloor \frac{n}{2} \right \rfloor }(-1)^{x-k}\binom{x}{k}\binom{n}{2x}(2x-1)!!\frac{(2n-3-2x)!!}{(2n-3)!!}$$ 时间复杂度 $O(n)$。 :::info[code] ```cpp //by lovely Autumn_Rain #include<bits/stdc++.h> using namespace std; #define ll long long #define For(i,l,r) for(int i=l;i<=r;i++) int n,m,k,p; const int N=5e6+10; ll fac[N],ifc[N]; ll f[N],g[N],s[N]; ll qpow(ll a,ll b){ ll res=1; while(b){ if(b&1)res=res*a%p; a=a*a%p; b>>=1; } return res; } ll C(int n,int m){ if(n<m||m<0)return 0; return (fac[n]*ifc[m]%p*ifc[n-m]%p)%p; } ll ans; int main(){ ios::sync_with_stdio(0); cin.tie(0);cout.tie(0); cin>>n>>k>>p;k=n-k; if(k*2>n){cout<<0<<'\n';return 0;} m=n>>1; For(i,1,m){ s[i]=s[i-1]+2*(n-2*i)+1; s[i]%=p; } fac[0]=f[0]=1; For(i,1,m){ fac[i]=i*fac[i-1]%p; f[i]=s[i]*f[i-1]%p; } ifc[m]=qpow(fac[m],p-2); g[m]=qpow(f[m],p-2); for(int i=m;i>=1;i--){ ifc[i-1]=i*ifc[i]%p; g[i-1]=s[i]*g[i]%p; } For(i,1,m){ ll t=1ll*(n-2*i+1)*(n-2*i+2)/2; f[i]=(t%p*f[i-1])%p; } For(i,k,m){ if((i-k)&1)ans=(ans+(2*p-C(i,k))*(g[i]%p*f[i]%p)%p)%p; else ans=(ans+C(i,k)*(g[i]%p*f[i]%p)%p)%p; } cout<<ans%p; return 0; } ``` :::