数论组合数
RNTBW
·
·
个人记录
组合数
C_n^m=\dfrac{n!}{m!(n-m)!}
C^m_n=C_{n-1}^{m-1}+C_{n-1}^m
\sum_{i=0}^nC_n^i=2^n
$\sum_{i=0}^n k\times C_n^k=n\times 2^{n-1}
\sum_{i=0}^n k^2\times C_n^k=n\times (n-1)\times 2^{n-2}
- 递推
？
- 预处理 N 以内的阶乘 fact_i 及阶乘的逆元
逆元递推式：inv_i=inv_{i+1}\times (i+1)
则 C_n^m=fact_n\times inv_m\times inv_{n-m}
复杂度 O(n+\log_2 p)。
注：模数必须为质数
- 玄学，玄学，还是玄学
可以对模数 p 分解质因数，对于每个 i 及每个质因数 pr_j，预处理出每个 i! 所包含的 pr_j 的数量记为 r_{i,j}。
我们来处理一下以下柿子：
\dfrac{n!}{m!}
=\dfrac{k\times pr_1^{x_1}\times pr_2^{x_2}....}{s\times pr_1^{y_1}\times pr_2^{y_2}....}
=k\times inv_s\times pr_1^{x_1-y_1}\times pr_2^{x_2-y_2}....
由于 k,s 中已经不包含任意的 p 的质因子了，所以 \gcd(k,p)=1,\gcd(s,p)=1。
这就意味着存在 inv_s\times s\equiv 1\pmod p。
可以预处理出 fact_n 及 fact_n 除去 p 的所有质因子后的逆元 inv_n，之后直接按照上述式子计算即可。
复杂度 O(n\log_2 n)，但是常数。
注：不要求模数为质数
思路：对于大质数 p 分解质因数，转化为
C_n^m\equiv a_i\pmod {pr_i}
其中 a_i=\dfrac{n!\bmod pr_i^{r_i}}{m!\bmod pr_i^{r_i}\times (n-m)!\bmod pr_i^{r_i}}
其中 n!\bmod p^k
=((p^k-1)!)^{n/p}\times (n/p)!\times (n\bmod p)!
注：这里的 ! 不带有 p 的倍数；(n/p)! 除外，它需单独计算
将 n!,m!,(n-m)! 组合起来即可
void init(int p,int pk)
{
fac[0]=1;
for(int i=1;i<=pk;i++)
{
fac[i]=fac[i-1];
if(n%p)fac[i]=fac[i]*i%pk;
}
}
int fir(int n,int p,int pk)
{
if(n==0)return 1;
int res=qm_n(fac[pk],n/pk,pk);
return res*fac[n%pk]%pk*fir(n/p,p,pk)%pk;
}
int sec(int n,int p)
{
if(n==0)return 0;
return n/p+sec(n/p);
}
void come_on(int n,int m,int p,int pk)
{
int k1=fir(n,p,pk);
int k2=inv(fir(m,p,pk),pk);
int k3=inv(fir(n-m,p,pk),pk);
int other=qm_n(p,sec(n,p)-sec(m,p)-sec(n-m,p),pk);
return k1*k2%pk*k3%pk*other%pk;
}
void exlucas(int n,int m,int p)
{
//对 p 分解质因数，a[i]=come_on(n,m,pr_i,pr_i^r_i),b[i]=pr_i
int res=1,x;ans=0;
for(int i=1;i<=cnt;i++) res*=b[i];
for(int i=1;i<=cnt;i++) x=inv(res/b[i],b[i]),ans=(ans+x*(res/b[i])%p*a[i]%p)%p;
//CRT
}//int128
可重集
1. 组合，数量无限：
考虑插板法，在 $n-1$ 个空位之中插入 $m-1$ 个板子
2. 组合，数量有限
考虑容斥，设第 $i$ 类不满足要求，可以预分配 $a_i+1$ 个
状压或深搜枚举不满足要求的 $i$，根据奇偶性容斥
其余皆按无限处理
3. 排列，数量有限
$\dfrac{n!}{\prod_{i=1}^m (a_i!)}
- 排列，数量无限
？
卡特兰数
指一类序列，为
1,1,2,5,14,42,132,429....
卡特兰数有许多模型：
- 走格子模型：
2. 括号序列：给定 $n$ 对括号求合法的括号序列数
3. $n+2$ 边形拆分问题
4. 买票找零问题
5. $n$ 个节点的无标号二叉树
卡特兰数有两种计算方式：
1. $C_{n+1}=\sum_{i=0}^n C_i\times C_{n-i}
代表模型：多边形拆分
-
C_{n}=C_{2n}^n-C_{2n}^{n-1}
代表模型：走格子
走格子推导过程：
其实这条黑线不一定要是对角线
设黑线在第一象限内与 x 或 y 轴的交点距原点 k
则答案为 C_{2n}^n-C_{2n}^{n-k-1}
球与盒子
主要有两个表：
$\color{red}empty:$ $\ $ **1. 球的排列有影响 2. 球的排列无影响**
**1. 盒子的排列有影响** $\ $ $m^n\qquad C_{n+m-1}^{m-1}
2. 盒子的排列无影响 \ \sum_{i=0}^m s2(n,i) \ \sum_{i=0}^m P(n,i) |
**3. 盒子的排列有影响** $\ $ $m!\times s2(n,m)\quad C_{n-1}^{m-1}
4. 盒子的排列无影响 \ s2(n,m) \quad P(n,m)
-
(3,4)
经典插板法，问题可以转化为这样：
上图即为 n=7,m=4 的情况。
问题转化为了在 n-1 个空位中插入 m-1 个木板，就可以将 n 个球分成 m 份，求方案数。
即为 C_{m-1}^{n-1}。
如果是 (1,2)（即可空），我们可以对于每个盒子预分配一个球，即多出 m 个球，按照上述方法计算即可。
事实上，这种模型也可以使用插板法：
_求 x_1+x_2+....+x_n=m 的正整数解的个数。_
这种情况下可以把 m 拆分为 m 个 1，即 m 个“球”，再插入 n-1 个木板，第 i 与第 i+1 块木板之间的 1 之和即为 x_{i+1}。
-
有一个明显的递推式：s2(n,m)=s2(n-1,m-1)+m\times s2(n-1,m)
考虑新加入一个球，这个球可以单独放入第 m 个盒子即 s2(n-1,m-1)。
也可以放在前面的盒子当中。
前面的 n-1 个球已经分配给了 m 个盒子，所以有 m 个放的地方，就是 m\times s2(n-1,m)。
其实我们可以联系上 (3,3)。
找规律可以发现，(3,3) 与 (4,3) 差了一个 m!。
而 (3,3) 就是这玩意。
而这个玩意儿可以使用容斥，枚举缺失了几个数来解决，有
m!\times s2(n,m)=\sum_{i=0}^m (-1)^i\times C_m^i\times (m-i)^n
$n$ 个位置可以任意取剩下的 $m-i$ 个数，即为 $(m-i)^n$。
所以 $s2(n,m)$ 可以用上述式子除上一个 $m!$ 得到，总时间复杂度 $O(m\log_2 n)$。
实际上，$(m-i)^n$ 甚至可以使用线性筛预处理，虽然不能完全 $O(m)$，但是常数比 $O(m\log_2 n)$ 小得多。
- $Bell$ 数
这玩意儿其实就是 $\sum_{i=0}^n s2(n,i)$。
它可以理解为把 $1,2,3,....$ 划分为 $m$ 个子集。
它有另外一个递推式：
$Bell_{n+1}=\sum_{i=0}^n C_n^i\times Bell_i$。
~~感性理解一下~~
关于这玩意儿，还有一个更离谱的东西：
它每行的第一个数和最后一个数都是 $Bell$ 数。
- 第一类斯特林数
它与前文提到的那玩意有什么区别呢？
第一类（$s1$）是⚪排列，$s2$ 是普通排列。
这就导致它的递推不一样：
$s1(n,m)=s1(n-1,m-1)+(n-1)$ (即为可以插入的位置的个数，在 $s1$ 里一个球即使被放入同一个盒子，位置不同也算作不同方案) $\times s1(n-1,m)$。
3. $(4,4)
什么是 P？
它可以理解为把一个自然数 n 拆分成 m 个数的方案。
有递推式：
P(n,m)=P(n-1,m-1)+P(n-m,m)
$P(n-m,m)$ 表示将之前 $n-m$ 分成 $m$ 块的所有方案中的所有数都加一个 1，加了 $m$ 个数然后块数不变
如果我们把 $n$ 分成任意块数，即自然数分解，答案就是 $\sum_{i=0}^m P(n-i)