组合数学学习笔记

· · 个人记录

p3744. 打扑克

直接递推了。

p3745. combination

使用卢卡斯定理切掉。

long long c(long long n,long long m)
{
    return f[n]*g[m]*g[n-m]%mod;
}
long long lcs(long long n,long long m)
{
    if(m==0)
        return 1;
    return lcs(n/mod,m/mod)*c(n%mod,m%mod)%mod;
}

3342. 【模板】卢卡斯定理/Lucas 定理

同上，只用改取模和输入。

P118. 「一本通 6.1 练习 3」越狱

结论：一共有 m^n 种可能，不可以越狱的可能，一共有 m*(m-1)^{n-1} 种。所以答案是二者相减。

原本需要扩展欧拉定理去算幂取模，但是对于这道题，快速幂解决即可。

p3749. Rooks LightOJ - 1005

对于 n 列，有 k 个需要摆放；对于 n 行，也需要摆放 k 个.

所以最终答案数是

\large C_{n}^{k}*A_{n}^{k}

要开 \text{long long} 。

P2280. 牡牛和牝牛

据说有 DP 做法，但是我不会。。

所以我选择组合数学推结论（洛谷上说不用卢卡斯定理，但是我还是用了）

结论:

ans=\sum_{i=0}^{n}\large C_{n-(i-1)\times k}^{ i}

对于 C ，卢卡斯秒了。但是好像不用。。。

3328. [ABC156E] Roaming

有点小难。。。

考虑 k 次移动后的空房子的最大值，显然是 k ，但是 k 有可能大于 n，所以是\min(k,n-1) 个，对于每个 i \in [0,\min(k,n-1) \ ]，答案个数是 \large C_{n}^{ \ i}（感性理解一下）

考虑 k 次移动后有人的房子，即是对于每个i \in [0,\min(k,n-1) \ ],n-1 个人会插在 n-i-1 个地方,答案个数是 \large C_{ \ n-1}^{ \ n-i-1} ，注意这里是 n-1 而不是 n-i 。。。

最终结果即是

\sum_{i=0}^{\min(n-1,k)} \large {(C_{n}^{i}\times C_{n-1}^{n-i-1}) }\text{ mod } p

p3751. X-factor Chain

结论题。

——msb大佬

输出的长度就是 n 的质因数个数（有重复）。

而第二个序列的个数就有一点难搞了：

从容斥的角度去想，这 k 个质因数想要排满，第一位有 1 种，第二位有 2 种，第 n 位就有 n 种，总共有 k! 种。

那么考虑以下情况：如果最后一位是 k_i ，那么前面的每一位都要有这个 k_i ，那么对于每一个 k_i ，就有 k_i! 种不合法的结果。（k_i 代表第 k 个质因数出现的个数）

即最终答案是：

\frac{k!}{\prod_{1}^{k}k_i!}

中间的细节，我没有记录每一个阶乘，都是现算的，但是能过。

P526. [HNOI2012]排队

纸张高精，抄的结论。

P2022. [Sdoi2016]排列计数

和上面的难度一样，都是绿题，但是这道题我一节课就推出来了。

首先，考虑先排在原位的数，即 a[i]=i 的那 m 个，显然，有 \large C_{ \ n}^{ \ m} 种。

接下来，考虑排剩下的不在原位的 n-m 个数，这里要求在剩下的位置里， a[i]!=i ，可以考虑错排法，结论：

D(i)= \begin{cases} 0&,i=1 \\ 1&,i=2 \\ (i-1)\times (D(i-1)+D(i-2))&,otherwise \end{cases}

证明可参考课件。

我们在处理 D(i) 的时候，需要用数组记忆化，处理 C 的时候，要用费马小定理求逆元。

最终答案即为：

C_{n}^{m}\times D(n-m) \mod (1e9+7)

P515. [ZJOI2010]Perm 排列计数

很有意思。题目的叙述转换成图论模型就是：求大小为 n 的小根堆有多少个。

需要树上 dfs ，用 lucas 算答案。

P2281. BZOJ 4403序列统计

依然是组合数。但是 lucas 的时候要有边界。。

3327. [ABC172E] NEQ

排列+错排。

考虑序列 A 的个数，显然是 A_{m}^{n} 种。

那么题目上说要求 \forall A_i \neq B_i,A_j \neq A_i,B_i\neq B_j

显然，B 序列是 A 的错排。在通常的定义中，错排 D(n)=(n-1)\times (D(n-1)+D(n-2)) 是针对于有 n 个可选数、且序列长度为 n 的。

但是这里是有 m 个可选数、且序列长度为 n，并有 m\ge n。

可以考虑加法原理，即 B 序列的选择数一定是 D(n)+f(n) 的形式，这里可以找个例子来理解一下：

若 n=3,m=4，则 A 序列的个数为 A_{m}^{n}=A_{4}^{3}=24。

对于一个 A=1,2,3，B 的全部合法序列为：

\begin{aligned} 2,3,4 \\ 2,4,1 \\ 2,3,1 \\ 3,4,1 \\ 3,2,4 \\ 3,4,2 \\ 3,1,2 \\ 3,1,4 \\ 4,3,1 \\ 4,1,2 \\ 4,3,2 \\ \end{aligned}

总共 11 种。可以看出，除过与 A 序列元素相同的排法，在第 N 位上，会有 m-n 个 A 序列中没有的元素，在本例中即是数字 4。而对于剩下 n-1 位，有 D(n-1) 种排法。

所以这道题的答案是错排公式是改编版( M,N 代表题中给出数据 ) ：

D(n)= \begin{cases} 1 &,n=0\\ M-N&,n=1 \\ (M-N)\times D(n-1)+(n-1)\times(D(n-2)+D(n-1))&,otherwise \end{cases}

P514. [SDOI2010] 古代猪文

小数论全家桶。但是比较简单。

答案显然是

\large G^{\sum_{d=1,d|n}^{n}C_{n}^{d}} \mod 999911659

但是直接使用逆元求 C 会炸时空。我们考虑扩展欧拉定理：

a^b \equiv a^{b \mod φ(m)} \pmod m,\gcd(a,m)=1

且由于 m=999911659 是个质数，所以 φ(m)=m-1=999911658

所以上式等价于：

\large G^{(\sum_{d=1,d|n}^{n}C_{n}^{d} )\mod 999911658} \mod 999911659

但 999911658 是个合数，所以我们把它进行质因数分解，这样就可以用 lucas 去求 C，然后用中国剩余定理合并答案即可。