计数原理

排列数公式：#

组合数公式：#

这里规定 #

一些比较重要的公式#

组合数取模#

1. • 利用杨辉三角求解

2. 是质数

   • 先求出阶乘，再求出阶乘的逆元
   • 先求出,然后计算d的逆元，继而利用的逆元求出等的逆元
   • 复杂度。

3. 是质数

   • 利用Lucas定理
   • 转到方法2
   • 复杂度

4. • 利用线性筛分解n!,计算每种质因子出现的次数,快速幕计算。
   • 质数数量为,复杂度为

5. 是质数

   • 由于涉及除法,所以考虑把存成不包含因子的部分和因子出现的次数处理。
   • 考虑每次把不包含因子的部分利用已预处理的阶乘计算,包含因子的部分可以写成公差为的等差数列,所以可以递归子问题,范围缩小为原来的,
     复杂度为

6. • 关键是计算,假设是完全平方数,否则暴力计算完全平方数以外的部分。
   • 构造多项式
   • 那么可得
   • 为阶多项式，现需要在个点求值
   • 现在的问题是多项式多点求值。
   • 为了描述方便,设给出多项式,求其在处的值。
   • 构造多项式
   • 那么，设
   • 由于模去了,所以的取值是不变的
   • 于是可以得到一个性质
   • 分治递归解决
   • 于是求解的复杂度为,问题解决。