以下部分内容摘自OI Wiki
排列数
从 \(n\) 个数中选出 \(m\) 个数按照一定的顺序排列，用 \(A_{n}^{m}\) 表示。排列的计算公式如下：
\(A_{n}^{m}=n(n-1)(n-2)...(n-m+1)=\dfrac{n!}{(n-m)!}\)。
组合数
从 \(n\) 个不同的元素中，选出 \(m\) 个元素组成一个集合，用 \(C_{n}^{m}\) 表示，也常用 \(\binom{n}{m}\) 表示。组合的计算公式如下：
\(C_{n}^{m}=\dfrac{n!}{m!(n-m)!}\)。
特别地，当 \(m>n\) 时，\(A_{n}^{m}=C_{n}^{m}=0\)。
插板法
插板法（Stars and bars）是用于求一类给相同元素分组的方案数的一种技巧，也可以用于求一类线性不定方程的解的组数。
正整数和的数目
问题一：现有 \(n\) 个 完全相同的元素，要求将其分为 \(k\) 组，保证每组至少有一个元素，一共有多少种分法？
这个问题的本质就是求 \(x_1+x_2+...+x_k=n\) 的正整数解的组数。
考虑在这些元素的 \(n-1\) 个空隙中插入 \(k-1\) 块板子，因为元素完全相同，那么答案就是 \(\binom{n-1}{k-1}\)。
非负整数和的数目
问题二：在问题一的基础上，允许每组元素为空。
本质就是求 \(x_1+x_2+...+x_k=n\) 的非负整数解的组数。
考虑先借来 \(k\) 个元素，在 \(n+k-1\) 个空隙中插入 \(k-1\) 个空格。最后再把借来的元素从每组中删去，即可满足题意。答案为 \(\binom{n+k-1}{k-1}\)。
不同下界整数和的数目
问题三：在问题二的基础上，要求第 \(i\) 组的元素数量至少为 \(a_i\)，满足 \(\sum a_i \leq n\)。
即求满足 \(x_i \geq a_i\)，\(x_1+x_2+...+x_k=n\) 的解的组数。
类比问题二，第 \(i\) 组先借来 \(a_i\) 个元素，令 \(x_i'=x_i-a_i\)，那么就有 \(x_i' \geq 0\)。得到新方程：
\(x_1'+x_2'+...+x_k'=n-\sum a_i\)。
那么问题转为求这个方程的非负整数解的组数。答案为 \(\binom{n-\sum a_i+k-1}{k-1}\)。
不相邻的排列
问题四：从 \(1 \sim n\) 中选 \(k\) 个不相邻的数，求方案数。
设第 \(i\) 个数与第 \(i-1\) 个数的间隔为 \(x_i\)，其中 \(x_1\) 表示第一个元素与 \(0\) 的间隔，\(x_{k+1}\) 表示最后一个元素与 \(n+1\) 的间隔。于是 \(x_1 \geq 0,x_{k+1} \geq 0\)，\(x_i \geq 1(i=2,3,4...k)\)。得到方程：
\(x_1+x_2+...+x_{k+1}=n-k\)。
令 \(x_1'=x_1+1\)，\(x_{k+1}'=x_{k+1}+1\)。
那么就转化为了问题一。答案就是 \(\binom{n-k+1}{k}\)。
二项式定理
\((a+b)^n=\sum_{i=0}^{n}\binom{n}{i}a^ib^{n-i}\)、
组合数的性质：
将选出的集合对全集取补集，数值不变：
\(\binom{n}{m}=\binom{n}{n-m}\) 。 \((1)\)
根据定义可以推出：
\(\binom{n}{k}=\frac{n}{k} \binom{n-1}{k-1}\) 。 \((2)\)
用杨辉三角的表达式，可以推出：
\(\binom{n}{m}=\binom{n-1}{m-1}+\binom{n-1}{m}\)。 \((3)\)
取二项式定理中 \(a=b=1\) 的特殊情况，可以得到：
\(\binom{n}{0}+\binom{n}{1}+...+\binom{n}{n}=\sum_{i=0}^{n} \binom{n}{i}=2^n\)。\((4)\)
同理，取二项式定理中 \(a=1,b=-1\) 的特殊情况，可以得到：
\(\sum_{i=0}^{n}(-1)^i\binom{n}{i}=[n==0]\)。\((5)\)
拆式子，感性理解一下可以得到：
\(\sum_{i=0}^{m} \binom{n}{i} \binom{m}{m-i}=\binom{n+m}{m}\)。\((6)\)
取 \((6)\) 中 \(n=m\) 的特殊情况，可以得到：
\(\sum_{i=0}^{n} \binom{n}{i}^2=\binom{2n}{n}\)。\((7)\)
通过对 \((4)\) 所对应的多项式函数求导，可以得到：
\(\sum_{i=0}^{n} i \binom{n}{i}=n2^{n-1}\)。\((8)\)
在 \(1\sim {n+1}\) 中选出 \(k+1\) 个元素，可以考虑枚举最大的元素的值，那么就得到等式：
\(\sum_{i=0}^{n} \binom{i}{k}=\binom{n+1}{k+1}\)。\((9)\)
在 \(n\) 个元素中选取 \(r\) 个元素，再在 \(r\) 中选取 \(k\) 个元素，等价于先选 \(k\) 个元素，再在剩下的 \(n-k\) 个元素中选取 \(r-k\) 个元素：
\(\binom{n}{r}\binom{r}[k]=\binom{n}{k}\binom{n-k}{r-k}\)。\((10)\)
而从杨辉三角上也不难发现：
\(\sum_{i=0}^{n}\binom{n-i}{i}=F_{n+1}\)。
其中 \(F\) 为斐波那契数列。
组合数问题
\(T\) 组询问，给定 \(n,m\) 和 \(k\)，对于所有的 \(0\leq i\leq n,0\leq j\leq \min \left ( i, m \right )\) 有多少对 \((i,j)\) 满足 \(k|\binom{i}{j}\)。
\(0 \leq n, m \leq 2 \times 10^3\)，\(1 \leq T \leq 10^4\)。
思路
注意到 \(n,m\) 的范围，同时 \(k\) 对于每一组询问相同。可以考虑 \(O(nm)\) 预处理出答案，\(O(1)\) 询问。
根据组合数在模 \(k\) 意义下的递推公式：
\(\binom{i}{j} =\left\{\begin{matrix} (\binom{i-1}{j-1}+\binom{i-1}{j}) \mod{k},j\in[1,i] \\ 1,j=0 \end{matrix}\right.\)
如果 \(\binom{i}{j}\) 在模 \(k\) 意义下为 \(0\)，那么显然就是一对满足题意的数对。只需要处理前缀和即可。
code：
#include<bits/stdc++.h>
using namespace std;
const int M=2e3+5;
int c[M][M],s[M][M],t,k,n,m;
int main()
{
cin>>t>>k;
for(int i=1;i<M;i++) c[i][0]=c[i][i]=1;
for(int i=1;i<M;i++)
for(int j=1;j<i;j++) c[i][j]=(c[i-1][j]+c[i-1][j-1])%k;
for(int i=1;i<M;i++)
{
for(int j=1;j<=i;j++)
{
s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1];
if(c[i][j]==0) s[i][j]++;
}
s[i][i+1]=s[i][i];
}
while(t--)
{
cin>>n>>m;
if(n<m) m=n;
cout<<s[n][m]<<endl;
}
}
回忆京都
\(q\) 次询问，每次询问求：
\(\sum_{i=1}^n \sum_{j=1}^m C^i_j\)，其中当\(i>j\)的时候，钦定\(C^i_j\)为\(0\)
\(1 \leq q \leq 10000,1 \leq n,m \leq 1000\)。
思路
可以直接预处理出 \(n,m\) 范围内的组合数，再用前缀和来统计答案。那么就是 \(O(nm)\) 预处理，单次询问的复杂度为 \(O(1)\)。
但我们也可以利用上面得到的等式 \((9)\)，对原式进行变换：
\(\sum_{i=1}^n \sum_{j=1}^m \binom{j}{i}=\sum_{i=1}^{n} \binom{m+1}{i+1}\)。
那么也可以做到 \(O(qn)\) 。
code：
#include<cstdio>
using namespace std;
const int mod=19260817,N=1050;
int c[N][N],s[N][N],n,m,q;
int main()
{
for(int i=0;i<N;i++)
for(int j=0;j<=i;j++)
if(!j) c[i][j]=1;
else c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;
for(int i=1;i<N;i++) for(int j=1;j<N;j++) s[i][j]=(s[i][j]+s[i-1][j]+s[i][j-1]-s[i-1][j-1]+c[i][j]+mod)%mod;
scanf("%d",&q);
while(q--)
{
scanf("%d%d",&m,&n);printf("%d\n",s[n][m]);
}
return 0;
}
Lucas定理
对于质数 \(p\)，有：
\(\binom{n}{m} \mod {p}=\binom{\lfloor n/p \rfloor}{\lfloor m/p \rfloor}\binom{n \mod {p}}{m \mod {p}} \mod {p}\)
吉夫特
题意比较繁琐，可以看原题题面。
思路：
应用 Lucas 定理， \(\binom{a_i}{a_j} \mod {2}=\binom{\lfloor a_i/2 \rfloor}{\lfloor a_j/2 \rfloor}\binom{a_i \mod {2}}{a_j \mod {2}} \mod {2}\)。
对于后面的 \(\binom{a_i \mod {2}}{a_j \mod {2}}\)，其取值有 \(\binom{1}{1},\binom{1}{0},\binom{0}{1},\binom{0}{0}\) 四种，其中只有 \(\binom{0}{1}=0\)。
不难发现，应用 Lucas 定理后就是将 \(a_i\) 与 \(a_j\) 在二进制下的每一位单独拎出来，为了避免出现 \(\binom{0}{1}\) 的情况，需要满足在二进制下，\(a_j\) 为 \(a_i\) 的子集。那么就可以用枚举子集的方法记录以每一个数结尾的方案数，最终的复杂度为 \(O(3^{\log_2 \max(a_i)})\)
code：
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=3e5+10,mod=1e9+7;
int n,x,f[N],ans;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;++i)
{
scanf("%d",&x);
for(int j=x-1&x;j;j=j-1&x) f[j]=(f[j]+f[x]+1)%mod;
ans=(ans+f[x])%mod;
}
printf("%d\n",ans);
return 0;
}