题面

Codejam

分析

一开始想了一堆奇怪的容斥，后来发现即使钦定每条边对应的是到哪个点的出边我也不会做

小清新计数题

首先注意到形成的图去掉方向后一定是森林，因为如果存在环 $u_1\stackrel{e_1}{\longrightarrow} u_2\stackrel{e_2}{\longrightarrow} u_3\cdots u_k\stackrel{e_k}{\longrightarrow} u_1$，假设边 $e$ 对应的边权为 $w\left(e\right)$，那么 $w\left(e_k\right)\gt w\left(e_{k-1}\right)\gt \cdots w\left(e_1\right)\gt w\left(e_k\right)$，矛盾！

且这个森林中每个弱联通块恰好存在一对点 $\left(u,v\right)$ 使得存在边 $u\rightarrow v,v\rightarrow u$，那么连通块的个数就恰好等于这样的点对数。

因此考虑上二项式反演，钦定 $t$ 个点对。此时我们把这 $t$ 个点对对应的 $t$ 条无向边按大小从小到大排个序，假设第 $i$ 小的边为 $e_i$，然后把图中 $\dfrac{n\left(n-1\right)}{2}$ 条边分成一下三类：

• 两个端点为同一个点对，即 $t$ 条无向边中的一个。
• 两个端点属于不同点对，假设对应的边分别为 $e_i,e_j$，那么这条边的边权 $w_0$ 满足 $w_0\lt w\left(e_{\min\left(i,j\right)}\right)$
• 两个端点中有一个属于某一个点对，假设对应的边为 $e_i$，那么这条边的边权 $w_0$ 满足 $w_0\lt e_i$
• 两个端点都不属于任何点对，那么这条边的边权任意。

那么可以发现，对于排名为 $i$ 的边 $e_i$，有 $n-2t+\left(t-i\right)\times 4$ 条边的限制为边权 $\lt w\left(e_i\right)$

而图合法的充要条件即为以上限制全部成立。总的有条件约束的边数为 $\sum_{i=1}^t\left(n-2t+\left(t-i\right)\times 4+1\right)=2tn-2t^2-t$

因此当前条件下符合条件的图个数为

$$ \begin{aligned} &\binom{\frac{n\left(n-1\right)}{2}}{2tn-2t^2-t}\left(\dfrac{n\left(n-1\right)}{2}-\left(2tn-2t^2-t\right)\right)!\prod_{i=1}^t\binom{\sum_{j=1}^i\left(n-2t+\left(t-j\right)\times 4+1\right)}{n-2t+\left(t-i\right)\times 4} \\=&\left(\dfrac{n\left(n-1\right)}{2}\right)!\cdot \dfrac{1}{\left(2tn-2t^2-t\right)!}\cdot \dfrac{\left(2tn-2t^2-t\right)}{\prod_{i=1}^ti\left(2n-2i-1\right)}\\ =&\left(\dfrac{n\left(n-1\right)}{2}\right)!\cdot\dfrac{\left(2n-2t-3\right)!!}{t!\left(2n-3\right)!!} \end{aligned} $$

而选 $t$ 个点对并排序的方案数为 $\displaystyle\binom{n}{2t}\cdot \left(2t-1\right)!!\cdot t!$

因此答案为

$$ \begin{aligned} &\dfrac{1}{\left(\frac{n\left(n-1\right)}{2}\right)!}\sum_{t=k}^{\left\lfloor\frac{n}{2}\right\rfloor}\left(-1\right)^{t-k}\binom{t}{k}\binom{n}{2t}\left(2t-1\right)!!\cdot t!\cdot\left(\dfrac{n\left(n-1\right)}{2}\right)!\cdot\dfrac{\left(2n-2t-3\right)!!}{t!\left(2n-3\right)!!} \\ =&\sum_{t=k}^{\left\lfloor\frac{n}{2}\right\rfloor}\left(-1\right)^{t-k}\binom{t}{k}\binom{n}{2t}\left(2t-1\right)!!\cdot \dfrac{\left(2n-2t-3\right)!!}{\left(2n-3\right)!!} \\ \end{aligned} $$

复杂度 $O\left(n\right)$

Code

#include <cstdio>
#include <algorithm>
using namespace std;
constexpr int N=500010,p=1000000007;
int ifac[N<<1],inv[N<<1],fac[N<<1],n,dfac[N<<1],difac[N<<1];
int binom(int a,int b){return 1ll*fac[a]*ifac[b]%p*ifac[a-b]%p;}
int main(){
    inv[1]=1;for(int i=2;i<(N<<1);++i) inv[i]=1ll*(p-p/i)*inv[p%i]%p;
    fac[0]=ifac[0]=1;for(int i=1;i<(N<<1);++i) fac[i]=1ll*fac[i-1]*i%p,ifac[i]=1ll*ifac[i-1]*inv[i]%p;
    difac[1]=1,dfac[1]=1;for(int i=3;i<(N<<1);i+=2) difac[i]=1ll*difac[i-2]*inv[i]%p,dfac[i]=1ll*dfac[i-2]*i%p;
    int T;scanf("%d",&T);
    for(int i=1;i<=T;++i){
        int n,k;scanf("%d%d",&n,&k);int ans=0;
        for(int k0=k;(k0*2)<=n;++k0){
            if((k0-k)&1) ans=(ans-1ll*binom(k0,k)*binom(n,2*k0)%p*dfac[2*k0-1]%p*difac[2*n-3]%p*(((2*n-2*k0-3)<0)?1:dfac[2*n-2*k0-3])%p+p)%p;
            else ans=(ans+1ll*binom(k0,k)*binom(n,2*k0)%p*dfac[2*k0-1]%p*difac[2*n-3]%p*(((2*n-2*k0-3)<0)?1:dfac[2*n-2*k0-3])%p)%p;
        }
        printf("Case #%d: %d\n",i,ans);
    }
    return 0;
}