/* MOD must be a prime*/
const int MOD = 1e9 + 7;
namespace Combinatory {
const int MAXN = 1e6 + 5;
ll qpow(ll x, ll n) {
if(x >= MOD) x %= MOD;
ll res = 1;
for(; n; x = x * x % MOD, n >>= 1)
if(n & 1) res = res * x % MOD;
if(res < 0) res += MOD;
return res;
}
ll inv(ll x) {
return qpow(x, MOD - 2);
}
ll fac[MAXN], invfac[MAXN];
void initC(int n) {
ASSERT(1 <= n && n <= MAXN && n < MOD);
fac[0] = 1, invfac[0] = 1;
for(int i = 1; i <= n; ++i)
fac[i] = 1LL * fac[i - 1] * i % MOD;
invfac[n] = inv(fac[n]);
for(int i = n - 1; i >= 0; --i)
invfac[i] = 1LL * invfac[i + 1] * (i + 1) % MOD;
}
ll A(ll n, ll m) {
ASSERT(fac[0] && n <= MAXN);
return (m < 0 || n < m) ? 0 : 1LL * fac[n] * invfac[n - m] % MOD;
}
ll C(ll n, ll m) {
ASSERT(fac[0] && n <= MAXN);
return (m < 0 || n < m) ? 0 : A(n, m) * invfac[m] % MOD;
}
// ll D[MAXN];
// void initD(int n) {
// ASSERT(1 <= n && n <= MAXN && n < MOD);
// D[0] = 1, D[1] = 0;
// for(int i = 2; i <= n; ++i) {
// if(i & 1) {
// D[i] = (1LL * i * D[i - 1] - 1) % MOD;
// if(D[i] < 0) D[i] += MOD;
// } else
// D[i] = (1LL * i * D[i - 1] + 1) % MOD;
// }
// }
}
using namespace Combinatory;
圆排列：n个不同的球，取m个进行圆排列，先用组合数取出m个，然后规定圆的开头是最小的元素，那么剩下的元素可以任意排列，故答案为 \(C_n^m\cdot A_{m-1}^{m-1}=\frac{n!}{(n-m)!m!}\cdot(m-1)!=\frac{n!}{(n-m)!m}=\frac{A_n^m}{m}\)
二项式反演：
若 \(f(n)=\sum\limits_{i=0}^{n}\binom{n}{i}g(i)\)
则 \(g(n)=\sum\limits_{i=0}^{n}(-1)^{n-i}\binom{n}{i}f(i)\)
通常用 \(f(i)\) 表示至多， \(g(i)\) 表示恰好，然后用二项式反演求出来。
这里的要求是这个系数恰好是二项式系数。
求至少的话，要再进行一套转换。
隔板法：x个相同的小球，有y个不同的盒子，每个盒子可以为空，求有多少种方案数？把y个不同的盒子视作y-1个不同的隔板，然后把小球视作不同的，全排列有 \(A_{x+y-1}^{x+y-1}\) 种，然后除以隔板的全排列（隔板之间没有区别），再除以小球的全排列（小球之间也没有区别），最后在两侧再加入两个隔板，然后两个隔板之间的就是这个盒子分配到的球数，也就是 \(C_{x+y-1}^{x}\) 。
常用的求和：
\(C_n^m = C _{n-1}^{m-1}+C _{n-1}^{m}\)
\(mC_n^m = nC _{n-1}^{m-1}\)
二项式定理： \(\sum\limits_{i=0}^nC_n^i=C_n^0+C_n^1+C_n^2+……+C_n^n = 2^n\)
类似求和 \(\sum\limits_{i=0}^n(-1)^iC_n^i=C_n^0-C_n^1+C_n^2-……+(-1)^nC_n^n = 0\) （奇数项求和=偶数项求和）
\(\sum\limits_{i=0}^n2^iC_n^i = 3^n\)
利用 \(C_n^mC_m^k=C_n^kC_{n-k}^{m-k}\) ，加上二项式定理，可以得到下式
\(1C_n^1+2C_n^2+3C_n^3+……+nC_n^n =n2^{n-1}\)
\(\sum\limits_{i=1}iC_n^i = \sum\limits_{i=1}C_i^1C_n^i = \sum\limits_{i=1}C_n^iC_i^1 \\ = \sum\limits_{i=1}C_n^1C_{n-1}^{i-1} = C_n^1\sum\limits_{i=1}^n C_{n-1}^{i-1} \\ = C_n^1\sum\limits_{i=0}^{n-1} C_{n-1}^i \\ = n2^{n-1} \\\)
\(1^2C_n^1+2^2C_n^2+3^2C_n^3+……+n^2C _n^n =n(n+1)2^{n-2}\)
\(\frac{C_n^1}{1}-\frac{C_n^2}{2}+\frac{C_n^3}{3}+……+(-1)^{n-1}\frac{C _n^n}{n} =1 + \frac{1}{2}+ \frac{1}{3}+……+ \frac{1}{n}\)
\((C_n^0)^2+(C_n^1)^2+(C_n^2)^2+……+(C _n^n)^2 = C_{2n}^n\)
n个球选x个染黑，黑球之间位置差至少为k的方案：在n-(x-1)(k-1)里面选x个黑球，染黑之后在前x-1个黑球后紧跟k-1个白球，得一一对应。