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

· · 题解

显然 G 无环，故问题等价于，求有恰好 n-k 条激活边的方案数。

2log 做法

考虑按照边权从大到小插入边，则一条边被激活，当且仅当两个点没有都被标记。随后，我们会标记这两个点。

发现前面的顺序不关心，只关心被标记的点集。

每次转移，选择至少一个点未覆盖的： 加入一条 $x$ 被覆盖，$y$ 没被覆盖，方案数 $i(n-i)$，即 $f_{i+1,j+1}\gets f_{i,j}\dfrac{2i}{n+i-1}

加入一条 x,y 都没被覆盖，方案数 \binom{n-i}{2}，即 f_{i+2,j+1}\gets f_{i,j}\dfrac{n-i-1}{n+i-1}。

那只需求出，f_{n,k} 的值。

朴素 DP 可以 O(n^2)，考虑分治 ntt 就可以做 2log，显然过不去。

线性做法

上面除了基础的观察，其余和正解无关。

相当于两个点都没有被标记的次数，就是连通块的个数。相当于加入了 k 条这样的边，记方案数为 f(k)。

考虑容斥，钦定加入了 k' 条这样的边，记对应方案数为 g(k)，则显然有 f(k)=\sum_{k'\ge k}(-1)^{k'-k}\binom{k'}{k}g(k')。

因此，我们只需要 O(n) 求出所有的 g。

考虑 g 怎么算，先选定这 k 条边对应的点集 S，然后相当于是取 n 个匹配的方案数，显然是 \binom{n}{2k}(2k-1)!!。

然后考虑如何确定剩余边的排名。容易发现目前这 k 条边怎么排都是对称的，我们任意钦定一种排法，最后乘以 k! 即可。

对于任意的一条未被钦定的边 (x,y)，则它的出现时间一定晚于 x 所在边 e_1 和 y 所在边出现时间 e_2 的最大值。不妨 e_1 出现晚于 e_2，则连边 e_1\to (x,y)，若不存在则连边 rt\to (x,y)。

显然还存在边 rt\to e_1\to e_2\to \cdots\to e_k，我们只需要求出这样建出的树的拓扑序概率，算一下发现应该是 \prod_{i=1}^k\dfrac{1}{\binom{n}{2}-\binom{n-2i}{2}}​。

由 \binom{n}{2}-\binom {n-2i}{2}=i(2n-2i-1)，综上可得：g(k)=\binom{n}{2k}(2k-1)!!\prod_{i=1}^k\dfrac{1}{2n-2i-1}。

因此 g 可以线性计算，时间复杂度 O(n)。

#include<bits/stdc++.h>
#define up(i,l,r) for(int i=(l);i<=(r);++i)
#define down(i,l,r) for(int i=(l);i>=(r);--i)
#define pi pair<int,int>
#define p1 first
#define p2 second
#define m_p make_pair
#define pb push_back
#define eb emplace_back
#define ppc __builtin_popcountll
using namespace std;
typedef long long ll;
inline ll read(){
    ll x=0;short t=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')t=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*t;
}
const int maxn=1e6+10,p=1e9+7;
int n,k,prd[maxn],g[maxn],fac[maxn],inv[maxn],ifac[maxn],fac2[maxn];
void init(){
    int n=1e6;
    fac[0]=1;up(i,1,n)fac[i]=fac[i-1]*1llu*i%p;
    inv[1]=1;up(i,2,n)inv[i]=(p-inv[p%i])*1llu*(p/i)%p;
    ifac[0]=1;up(i,1,n)ifac[i]=ifac[i-1]*1llu*inv[i]%p;
    fac2[0]=1;up(i,1,n)fac2[i]=fac2[i-1]*1llu*(2*i-1)%p;
}
inline int C(int n,int m){return fac[m]*1llu*ifac[n]%p*ifac[m-n]%p;}
int T;
void slv(){
    n=read(),k=read();
    prd[0]=1;up(i,1,n/2)prd[i]=prd[i-1]*1llu*inv[2*n-2*i-1]%p;
    up(i,1,n/2)g[i]=prd[i]*1llu*fac2[i]%p*C(2*i,n)%p;
    int res=0;
    up(i,k,n/2){
        int v=g[i]*1llu*C(k,i)%p;
        if((i-k)&1)v=p-v;
        (res+=v)%=p;
    }printf("Case #%d: %d\n",++T,res);
}
int main(){
    // freopen("1.in","r",stdin),freopen("1.out","w",stdout);
    init();int t=read();while(t--)slv();
    return 0;
}