组合数公式
我们考虑这样一个场景，有 \(n\) 个不同的小球，从中不放回地取出 \(m\) 个，不考虑取出顺序有多少种不同的取法。学习过组合数学的人会回答，是 \(C_{n}^{m}=\frac{n!}{m!(n-m)!}\) ，其中 \(n!\) 是 \(n\) 的阶乘，其值为 \(n! = n \times (n-1) \times \dots \times 2 \times 1\) 。我们将 \(C_{m}^{n}\) 这样的公式称为组合数公式。
组合数公式的性质
假设 \( n\geq 0,m\geq 0,\)
1.对于任意 \(n\) ，有 \(C_{n}^{0}=C_{n}^{n}=1\)
2.对于任意 \(m\leq n\) ，有 \(C_{n}^{m}=C_{n}^{n-m}\)
3.当 \(m>0\) 时,有 \(C_{n}^{m}=C_{n-1}^{m-1}+C_{n-1}^{m}\)
性质3是组合数公式的递推式，还有一个更为人所知的叫法是杨辉三角。在 \(m,n\) 比较小且需要求很多组组合数的时候，往往可以使用这个性质。至于 \(n>0\) ，小心数组越界！
4.二项式定理： \( (x+y)^n=\sum\limits_{m=0}^{n}C_{n}^{m}x^{m}y^{n-m}\)
令二项式定理中的 \(x=y=1\) ，还能得出：\( \sum\limits_{m=0}^{n}C_{n}^{m}=2^n\)
怎么求组合数
1.暴力公式求解
根据组合数公式的定义 \(C_{n}^{m}=\frac{n!}{m!(n-m)!}\) ，只需要分别求出 \(n!,m!,(n-m)!\) 就可以直接求出组合数。
优点：简单暴力。缺点：一次只能求一个，\(n,m\) 很大的时候跑的很慢。
2.递推求解
根据组合数公式的递推式 \(C_{n}^{m}=C_{n-1}^{m-1}+C_{n-1}^{m}\) 以及性质1,可以用二重循环递推求出某一 \(n,m\) 范围内的组合数。
优点：简单暴力，预处理后能在 \(O(1)\) 复杂度查询，缺点：因为是二重循环只要 \(n,m\) 稍微大点就会跑的很慢然后TLE。
3.模意义下的乘法逆元
设有一质数为 \(p\) ，阶乘 \(fac_{n}=n!\) ，根据费马小定理其乘法逆元 \(inv_{n}=pow(fac_{n},p-2)\) ，根据组合数公式的定义 \(C_{n}^{m}=\frac{n!}{m!(n-m)!}\) 及模意义下的乘法逆元，有 \(C_{n}^{m}\equiv \frac{n!}{m!(n-m)!} \equiv fac_{n} \times inv_{m} \times inv_{n-m}(mod\ p)\)。如果使用费马小定理来求逆元，那么每次询问需要 \(O(log\ p)\) 的复杂度跑快速幂。
long long ksm(long long x, int p, int mod)
{
long long ans = 1;
while (p)
{
if (p & 1) ans = (ans * x) % mod;
x = (x * x) % mod;
p >>= 1;
}
return ans % mod;
}
long long c(int n, int m, int p)//求组合数c[m][n]
{
return (n > m) ? 0ll : (fac[m] * ksm(fac[n], p - 2, p) % p) * ksm(fac[m - n], p - 2, p) % p;
}
另外询问数量级很大的话可以考虑通过线性递推预处理出阶乘的逆元 \(inv_{n}\) ，这样查询就是 \(O(1)\) 复杂度了。
优点：跑得比较快，相对简单，缺点：需要结果对质数取模时才能使用，需要 \(O(n)\) 的预处理，不适用于 \(n\) 特别大的情况。
4.Lucas公式
设有一质数 \(p\) ，根据Lucas公式，有 \(C_{n}^{m}\equiv C_{n/p}^{m/p}\times C_{n\ mod\ p}^{m\ mod\ p}(mod\ p)\) ，换个表示形式就是 \(C_{sp+q}^{tp+r}\equiv C_{s}^{t}\times C_{q}^{r}\) 。
一般来说我们需要利用乘法逆元求 \(C_{n\ mod\ p}^{m\ mod\ p}\) 的结果，这要求了模数 \(p\) 不能太大，否则很难求出这部分组合数。然后 \(C_{n/p}^{m/p}\) 的部分，我们可以用递归的形式求取，一般递归结束的条件是 \(m/p\leq 0\) 。
long long lucas(int n, int m, int p)//求组合数c[m][n]
{
return n ? lucas(n / p, m / p, p) * c(n%p, m%p, p) % p : 1ll;
}
优点：只要 \(p\) 足够小，就可以在 \(log_{p}\ n\) 的时间复杂度内求出模意义下的结果，缺点：需要结果对质数取模时才能使用，模数 \(p\) 不能太大。
Lucas定理
上面已经提到过了使用Lucas定理来求组合数，设有一质数 \(p\) ，有 \(C_{n}^{m}\equiv C_{n/p}^{m/p}\times C_{n\ mod\ p}^{m\ mod\ p}\) ，换个表示形式就是 \(C_{sp+q}^{tp+r}\equiv C_{s}^{t}\times C_{q}^{r}\) 。这里主要给出其证明和一些其他应用。
证明
首先我们需要证明在 \(1\leq i\leq p\) 时， \(C_{p}^{i}=\frac{i}{p}\times C_{i-1}^{p-1}\) 。
证明如下 \(C_{p}^{i}=\frac{p!}{i!(p-i)!}=\frac{p}{i}\times\frac{(p-1)!}{(i-1)![(p-1)-(i-1)]!}=\frac{i}{p}\times C_{i-1}^{p-1}\) 。
然后考虑二项式公式 \( (1+x)^p=\sum\limits_{m=0}^{p}C_{p}^{m}x^{m}\) ，将中间 \(x^1 \dots x^n\) 项用式 \(C_{p}^{i}=\frac{i}{p}\times C_{i-1}^{p-1}\) 变换后，易知其系数模 \(p\) 等于 \(0\) 。用数学的式子表示出来就是 \( (1+x)^p\equiv C_{p}^{0}x^0+C_{p}^{p}x^p\equiv 1+x^p(mod\ p)\) 。
有人可能会说，哎分母不是还有一个 \(i\) 吗,怎么就易知其系数模 \(p\) 等于 \(0\) 了？其实很简单，已知 \(C_{p}^{i}\) 是一个整数，那么 \(\frac{p}{i}\times C_{p-1}^{i-1}\) 也应该是一个整数，因为 \(p\) 是一个整数的同时也是一个质数，那么为了保证乘积是一个整数， \(\frac{C_{p-1}^{i-1}}{i}\) 也必须是一个整数，这样 \(C_{p}^{i}\) 就被表示为了 \(p\) 乘以一个整数的形式，因此它模 \(p\) 等于 \(0\) 。
书接上文，令 \(n=sp+q,m=tp+r\) ，将 \( (1+x)^n\) 展开,
\( (1+x)^n=((1+x)^p)^s\times (1+x)^q\) ,
\( ((1+x)^p)^s\equiv (1+x^p)^s(mod\ p)\) ,
所以 \( (1+x)^n\equiv (1+x^p)^s\times (1+x)^q(mod\ p)\) ,
等式左边是二项式，等式右边是两个二项式的乘积，我们将它们展开，观察等式两边 \(x^m\) 的系数，
\(C_{n}^{m}\times x^b \equiv C_{s}^{t}x^tp \times C_{q}^{r}x^r \equiv C_{s}^{t}\times C_{q}^{r}\times x^{tp+r}(mod\ p)\)其中， \(x^{tp+r}=x^b\) ，因此 \(C_{n}^{m}\equiv C_{s}^{t}\times C_{q}^{r}\equiv C_{n/p}^{m/p}\times C_{n\ mod\ p}^{m\ mod\ p}(mod\ p)\)。
Lucas定理求组合数奇偶性
求 \(C_{n}^{m}\) 的奇偶性，利用Lucas定理，令 \(p=2\) ，则有 \(C_{n}^{m}=\prod\limits_{i=1}C_{n_i}^{m_i}\)，其中 \(n_i,m_i\) 是 \(n,m\) 二进制下第 \(i\) 位的数。因为 \(n_i,m_i\) 都为 \(0\) 或 \(1\) ，考虑它们的四种排列组合，但且仅当 \(n_i=0,m_i=1\) 时， \(C_{n_i}^{m_i}=0\) ，其余组合的情况下 \(C_{n_i}^{m_i}=1\) 。考虑到只要连乘因子中存在一个 \(0\) ，乘积就为偶数。因此，当且仅当 \(n_i \land m_i=n_i\)时，对于所有 \(i\) 有 \(C_{n_i}^{m_i}=1\) ，即 \(n \land m=n\) 时，\(C_{n}^{m}\) 为奇数，反之为偶数。
Lucas定理例题
题意简述
有 \(t(t\leq 10^5)\) 组数据，对于每组数据给定 \(n,k(n,k\leq 10^{18})\) ，求 \(\sum\limits_{i=0}^{k}C_{n}^{i}\bmod 2333\) 。
分析
本题的 \(n,k\) 都很大，还要求连续一段组合数的和，显然不能直接求。然后模数是一个很小的素数，有应用Lucas定理的可能。先尝试对原式进行化简。
令 \(p=2333\) ， \(\sum\limits_{i=0}^{k}C_{n}^{i}\equiv \sum\limits_{i=0}^{k}(C_{n/p}^{i/p}\times C_{n \bmod p}^{i \bmod p})(\bmod p)\) ，考虑整除分块，每 \(p\) 个和分为一块，
\(原式\equiv C_{n/p}^{0} \sum\limits_{i=0}^{p-1}C_{n\bmod p}^{i\bmod p}+C_{n/p}^{1} \sum\limits_{i=p}^{2p-1}C_{n\bmod p}^{i\bmod p}+\dots +C_{n/p}^{k/p-1} \sum\limits_{i=(k/p-1)p}^{(k/p)p-1}C_{n\bmod p}^{i\bmod p}+C_{n/p}^{k/p}\sum\limits_{i=(k/p)p}^{k}C_{n\bmod p}^{i\bmod p}\) \(\equiv C_{n/p}^{0} \sum\limits_{i=0}^{p-1}C_{n\bmod p}^{i}+C_{n/p}^{1} \sum\limits_{i=0}^{p-1}C_{n\bmod p}^{i}+\dots +C_{n/p}^{k/p-1} \sum\limits_{i=0}^{p-1}C_{n\bmod p}^{i}+C_{n/p}^{k/p}\sum\limits_{i=0}^{k\bmod p}C_{n\bmod p}^{i}\) \(\equiv (C_{n/p}^{0}+C_{n/p}^{1}+\dots +C_{n/p}^{k/p-1})\sum\limits_{i=0}^{p-1}C_{n\bmod p}^{i}+C_{n/p}^{k/p}\sum\limits_{i=0}^{k\bmod p}C_{n\bmod p}^{i}\) \(\equiv \sum\limits_{i=0}^{k/p-1}C_{n/p}^{i}\sum\limits_{i=0}^{p-1}C_{n\bmod p}^{i}+C_{n/p}^{k/p}\sum\limits_{i=0}^{k\bmod p}C_{n\bmod p}^{i}(\bmod p)\)我们发现，在上式中，存在多个类似于 \(\sum\limits_{i=0}^{y}C_{x}^{i}\) 形式的式子，我们将这样的式子记作 \(f(x,y)\) ，那么刚才的式子就可以写成 \(f(n/p,k/p-1)\times f(n\bmod p,p-1)+C_{n/p}^{k/p}\times f(n\bmod p,k\bmod p)\) 。
考虑到 \(p\) 的值较小且固定，其中 \( f(n\bmod p,p-1)\) 和 \(f(n\bmod p,k\bmod p)\) 可以通过预处理所有 \(f(0,0)~f(p,p)\) 的情况直接得出。而 \(C_{n/p}^{k/p}\) 可以通过Lucas定理求出。那么就只剩下 \(f(n/p,k/p-1)\)这项不好直接求出了。
考虑到我们要求的原式为 \(\sum\limits_{i=0}^{k}C_{n}^{i}\bmod 2333\) ，它也可以写成 \(f(n,k)\) 的形式，那问题就可以使用递归来解决了。
参考代码
template<typename T>
inline T read()
{
T x = 0;
bool f = 0;
char ch = getchar();
while (ch < '0' || ch>'9')
{
if (ch == '-') f = 1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
{
x = (x << 3) + (x << 1);
x += ch ^ 48;
ch = getchar();
}
return f ? -x : x;
}
const int MAXN = 3000;
const int long long p = 2333;
long long fac[MAXN];
long long f[MAXN][MAXN];
void init()
{
fac[0] = 1;
for (int i = 1; i <= p; i++)
{
fac[i] = (fac[i - 1] * i) % p;
}
for (int i = 0; i <= p; i++)
{
f[i][0] = 1;
for (int j = 1; j <= i; j++)
{
f[i][j] = (f[i - 1][j - 1] + f[i - 1][j]) % p;
}
}
for (int i = 0; i <= p; i++)
{
for (int j = 1; j <= p; j++)
{
f[i][j] = (f[i][j] + f[i][j - 1]) % p;
}
}
}
long long ksm(long long x, long long po)//快速幂用于费马小定理求逆元
{
long long ans = 1;
while (po)
{
if (po & 1) ans = (ans * x) % p;
po >>= 1;
x = (x * x) % p;
}
return ans;
}
long long c(long long n, long long m)//求组合数c[m][n]
{
return n > m ? 0ll : fac[m] * ksm(fac[n], p - 2) % p * ksm(fac[m - n], p - 2) % p;
}
long long lucas(long long n, long long m)//求组合数c[m][n]
{
return n ? lucas(n / p, m / p) * c(n % p, m % p) % p : 1ll;
}
long long solve(long long k, long long n)//求f(n,k)
{
if (k < 0) return 0ll;
if (!k) return 1ll;
if (!n) return 1ll;
if (n < p && k < p) return f[n][k];
return (solve(k / p - 1, n / p) * f[n % p][p - 1] % p + lucas(k / p, n / p) * f[n % p][k % p] % p) % p;
}
int main()
{
init();//预处理
int t = read<int>();
while (t--)
{
long long n = read<long long>(), k = read<long long>();//读入
long long ans = solve(k, n);
printf("%lld\n", ans);
}
return 0;
}
Comments NOTHING