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。。
