UESTC 1888. Birthday Party

Brief description:

…。n 个点。每个点随机向某个自己以外的点连一条边。。
。。问存在一个 k 元环的概率。。
。。(n, k = 10^7 。。。。

Analysis:

… 我是傻逼。

首先。。如果只有一个环。(当 $$k >\lfloor n/2\rfloor$$ 时。。。
。。的时候很好解决。。就是。。

$$!\binom{n}{k}(k-1)!(n-1)^{n-k}$$

。。如果不止有一个环。。那么对任意一个含有 $$i$$ 个环的解。。上面的公式会计数 $$\binom{i}{1}$$ 次。
。。至此容斥原理就很明显了。

。再考虑两个环的情况。。。

$$!\binom{n}{k}\binom{n-k}{k}\frac{(k-1)!^2}{2!}(n-1)^{n-2k}$$
。。注意除以 $$2! $$ 因为一组含有 $$i$$ 个环的方案会被计数 $$i! $$ 。。(我一开始少了这个 WA 成狗。。、、。

。。我们顺便把总的方案数 $$(n-1)^n$$ 考虑进去。。一般的。。有。。。。

$$!\frac{n!(k-1)!^i(n-1)^{n-ik}}{(n-ik)!i!k!^i(n-1)^n}$$

。。化简以后得。。。

$$!\frac{n!}{(n-ik)!i!k^i(n-1)^{ik}}$$

。。但是这样直接算阶乘精度上会跪。。。(仰慕核武!。
。。。设 $$A_i$$ 表示有 $$i $$ 个环时的含重方案数。。。
。。。。再把递推式搞出来就行了。。。。

$$!A_n=\begin{cases}\qquad\qquad 1 &n=0\\ \\ \\ \frac{\prod_{t=n-ik+1}^{n-(i-1)k}A_{n-1}}{ik(n-1)^k} &n \geq 1\end{cases}$$

/* .................................................................................................................................. */

const int N = 10000009;

DB f(){
    int n, k; RD(n, k); DB res = 0, cur = 1; int t = n; REP_1_C(i, n/k){
        cur /= i*k; DWN_1_C_N(t, t, t-k+1) cur *= (DB)t/(n-1);
        if (i&1) res += cur; else res -= cur;
    }
    return res;
}

int main(){

#ifndef ONLINE_JUDGE
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif

    Rush OT(f());
}

容斥原理
。。(本来是 DIY 群里 HaibaraAi 问我的问题。。。结果 TA 在我 debug 出来前一天好像就已经 AC 了。。。Orz。。

External link:

http://acm.uestc.edu.cn/#/problem/show/747