搜索什么...
数学笔记——组合计数
啊~我讨厌数学 ——沃若老师 本笔记讲述了与组合计数有关的内容！ 组合数 $$C(n,m)=C(n,n-m)=\frac{n!}{(n-m)!m!}$$ 其中 $n!=n\times(n-1)\times(n-1)\times\dotsc\times 1$，为了使 $n!=n\times(n-1)!$ 成立我们令 $0!=1$ 组合数的递推公式（可用作预处理）时间复杂度 $O(nm)$： $$C(n,m)=C(n-1,m)+C(n-1,m-1)$$ 当然在给定模数的情况下你也可以预处理阶乘和阶乘的逆元，时间复杂度下降到 $O(n)$ 可重排列 考虑有 $n$ 个球，第 $i$ 种球有 $a_i$ 个…
0 2023-08-13数学笔记——不定方程、同余、欧拉函数、逆元、中国剩余定理
介绍了不定方程、同余、欧拉函数、逆元、中国剩余定理的相关知识 不定方程 形如 $ax + by = c$，其中 $a$, $b$, $c$ 是已知数的方程被称为二元一次不定方程。它有解当且仅当 $\gcd(a,b)\mid c$ 我们可以通过扩展欧几里得算法求不定方程： void exgcd(int a, int b, int &x, int &y) { if (a % b == 0) { x = 0; y = 1; } else { exgcd(b, a % b, y, x); y -= a / b * x; } } 同余 这是一个同余式： $$a \equiv b \pmod p $$ …
1 2023-08-08