数学笔记——组合计数
啊~我讨厌数学 ——沃若老师 本笔记讲述了与组合计数有关的内容！ 组合数 $$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洛谷虚拟赛-5总结
洛谷虚拟赛-5的总结 分数 & 排名 预期分数： $$ 100+100+50+20=270 $$ 实际分数： $$ 100+100+40+30=270 $$ 排名 $10$ 分析 T1 真的在送分 确实是‘在送分’，写个桶或是map就可以了 string s; cin >> s; int ss = s.size(), ans = 0; for (int i = 0; i < 26; ++i) t[i] = false; for (int i = 0; i < ss; ++i) if (!t[s[i] - 'A']) t[s[i] - 'A'] = true, ++ans; cout << ss << ' ' << a…
1 2023-03-18虚拟赛-1总结
洛谷虚拟赛-1的总结 分数 & 排名 预期分数： $ 100+100+100+?=3?0 $ 实际分数：$ 100+100+70+40=310 $ 排名第五 分析 第一题和第二题比较简单，都对。 第三题由于使用了暴力解法，#15~#20出现了超时的现象。本来以为 $ 3000 $ 的数据范围 $ 3000 \times 3000 \times 3000=3 \times 10^9 $ 勉强能卡过（以为 $ 10^9 $ 可以在一秒内运行），可实际不能，而且 $ \gcd $ 的复杂度没有考虑。 第四题看到“最大值尽量小”就想到了二分，二分写得也是…
0 2023-01-19C++ STL那些事
仍在施工中 介绍C++ STL的一些函数和容器的用法。 简介 C++ Standard Template Library（标准模板库），简称 STL 成员 容器 map 有建立映射的关系。对于每一个 $key$ 有一个 $value$ 与之对应。 $$ key -> value $$ 时间复杂度 $ O(log_n) $ 使用前包含头文件 <map> #include<map> 比如我们新建了一个 map 叫 m，$key$ 是 string 类型，$key$ 是 int 类型，可以这么写： map <string, int>m; m.find(x)：传入 $k…
0 2023-01-18