做个备忘录把......
二项式反演:
令 \(f_i\) 表示至少选择 \(i\) 个,\(g_i\) 表示敲好选择 \(i\) 个
- \(f_i=\sum_{
- j=0
- }^i \dbinom{
- n
- }{
- j
- }*g_j\)
- \(g_i=\sum_{
- j=0
- }^{
- i
- }(-1)^{
- i-j
- }\dbinom {
- n
- }{
- j
- }f_j\)
范德蒙德卷积:
\(\dbinom{n}{k}=\sum_{i=0}^k\dbinom{m}{i}*\dbinom{k-i}{n-m}\)
组合数无名公式:
\(\dbinom{m}{i}*\dbinom{i}{j}=\dbinom{m}{i}*\dbinom{m-j}{i-j}\)
中国剩余定理:
- \(M_i=lcm/m_i, x_i=M_i^{
- -1
- }(mod\ m_i)\)
- \(Ans=\sum_{
- i=1
- }^n x_i*a_i*M_i(mod\ lcm)\)
第二类斯特林数:
- \(S(n, m)=\dfrac{
- 1
- }{
- m!
- }*\sum_{
- k=0
- }^m(-1)^k*\dbinom{
- m
- }{
- l
- }*(m-k)^n\)
- \(n^k=\sum_{
- i=0
- }^kS(k, i) * i! *\dbinom{
- n
- }{
- i
- }\)
康拓展开:
\(\sum_{i=1}^n(s_i-\sum_{j=1}^{i-1}[s_j<s_i])*(n-i+1)!\)
拉格朗日插值:
\(f(k)=\sum_{i=0}^ny_i* \prod_{i!=j}\dfrac{k-x_j}{x_i-x_j}\)
数论小节
来源: http://www.bubuko.com/infodetail-3267251.html