标签：总结 2024.3 frac times 长度 错排 dp equiv

今天学组合数学

\(C(n, m)\)表示 \(n\) 个物品里面选 \(m\) 个的方案数
\(C(n, m) = C(n - 1, m) + C(n - 1, m - 1) = \frac{n!}{m! \times（n-m)!}\)

第一题：

前提条件是互质。
F1： \(n^{-1} \equiv n^{p-2} \pmod p\)
F2: 设 \(a = \lfloor p/i\rfloor, b = p % i\)

\[a \times i + b = p \]

\[a \times i + b \equiv 0 \pmod p \]

\[a \times i \equiv -b \]

\[\frac{i}{b} \equiv -a^{-1} \]

\[\frac{b}{i} \equiv -a \]

\[i^{-1} \equiv -a \times b^{-1} \]

所以 \(dp\) 式子为\(dp_i = (p - p \div i) * dp_{p \mod i} \mod p\)

第二题：

\(i!\) 的乘法逆元就是\((i-1)!\)的乘法逆元乘以\(i\)的乘法逆元

第三题：

拿样例来说先放\(a\)的放发为\(C(5, 3)\)，接下来放\(b\)的概率就是\(C(2, 1)\)，\(c\)就是\(C(1, 1)\)
牛逼点说就是假设当前还空余的位置有\(k\)个，当前字母的出现次数为\(n\)那么这些字母的摆放方案为\(C(k, n)\)，然后\(k\)减去\(n\)

第四题：

隔板法
看作\(m+1\)个空插\(n-1\)个板，允许多个板插在同一个地方，这样我们无法处理有\(0\)个的情况，所以我们每人加一个全息投影的苹果保证每人至少有一个，现在问题就变成了\(m + n - 1\)个空插\(n - 1\)个板，这样答案就是\(C(m + n - 1, n - 1)\)

第五题：

证明：\((a + b) ^ n\)展开后所得的系数为杨辉三角的第\(n\)层。
\((a + b) ^ n\)可以看成$$(a + b) \times (a + b) \dots \times (a + b)$$
共\(n\)个，那么\(a^x \times b^y\)的系数就是每次在\(a\)和\(b\)中选则然后组成，那么系数就是方案数就是\(C(n, x)\)

第六题：

斜着看发现是杨辉三角

第七题:

考虑递推，那么长度为\(i\)的错排就可以是长度为\(i - 1\)的错排中的任意一个数与\(i\)交换而来，如果长度为\(a - 1\)的串中有一对元素与坐标相等，那么必须将\(i\)与那个数交换，这样就剩下了一个长度为\(i - 2\)的错排
注意：长度为0的错排有一个，长度为1的没有。

第八题：

那就是一个长度为 \(n - m\)的错排，然后接下来\(m\)个在\(n\)个里面随便放。

标签：总结,2024.3,frac,times,长度,错排,dp,equiv
From： https://www.cnblogs.com/libohan/p/18054511