组合数学

• \(A_n^m=\frac{n!}{(n-m)!}\) 表示在 \(n\) 个不同的元素中选出 \(m\) 个元素的排列数
• \(C_n^m=\frac{A_n^m}{m!}=\frac{n!}{m!(n-m)!}\) 表示在 \(n\) 个不同的元素中选出 \(m\) 个元素的方案数
• 二项式定理：\((a+b)^n=\sum C_n^i a^i b^{n-i}\)，\(2^n=\sum C_n^i\)
• 扩展：
  \((\sum_{i=1}^t x_i)^n = \sum_{ \sum n_i=n(0\le n_i)} \frac{n！}{n_1!n_2!\cdots n_t!} x_1^{n_1}x_2^{n_2}\cdots x_t^{n_t}\)

组合数练习

• 问题 \(1\)：有 \(n\) 个完全相同的苹果，分到 \(m\) 个盘子且没有空盘子的方案数。
  • 问题相当于在一段苹果序列中插入 \(m-1\) 个板子，使得苹果被分成 \(m\) 份，每一份苹果对应一个盘子。
  • \(Ans=C_{n-1}^{m-1}\)
• 问题 \(2\)：存在空盘子的方案数
  • 我们考虑先借来 \(m\) 个苹果，然后可以先按问题 \(1\) 考虑，之后还回去 \(m\) 个苹果
  • \(Ans=C_{n+m-1}^{m-1}=C_{n+m-1}^n\)
• 问题 \(3\)：对于第 \(i\) 个盘子，至少要有 \(a_i\) 的苹果
  • 我们先借 \(\sum a_i\) 个苹果，然后变为问题 \(2\)
  • \(Ans=C_{n-\sum a_i+m-1}^{n-\sum a_i}\)
• 不相邻的排列：\(1 \sim n\) 这 \(n\) 个自然数中选 \(k\) 个，使得 \(k\) 个数中任何两个数都不相邻的方案数
  • 对于每一个选的数，我们可以默认先选择当前数前面的点，而由于开头可以不空所以 \(+1\)
  • \(Ans=C_{n-k+1}^k\)

反演

单位根反演

单位根与原根

• 单位根：\(w_n^k=cos(\frac{2k\pi}{n})+i·sin(\frac{2k\pi}{n})=e^{i·\frac{2k\pi}{n}}\)
  • \(w_n^xw_n^y=x_n^{x+y}\)，\((w_n^x)k=w_n^{xk}\)，\(w_n^k=w_n^{k\bmod n}\)，\(|w_n^k|=1\)
• 原根：\(w_n^k=g^{k\frac{p-1}{n}}\)

原理

• \([n\mid k]=\frac{1}{n}\sum_{i=0}^n w_n^{ik}\)
  • 若 \(n\mid k\)，则 \(w_n^{ik}=w_n^0=1\)，则原式等于 \(1\)
  • 若 \(n\nmid k\)，则 \(\frac{w_n^{kn}-1}{w_n^k-1}\)，由于分子为 \(0\)，则原式等于 \(0\)

结论