摘要: LGV引理 阅读全文
posted @ 2026-05-10 00:18 qwynick 阅读(3) 评论(0) 推荐(0)
摘要: 拆分数 阅读全文
posted @ 2026-05-10 00:18 qwynick 阅读(3) 评论(0) 推荐(0)
摘要: 斯特林数 阅读全文
posted @ 2026-05-10 00:17 qwynick 阅读(4) 评论(0) 推荐(0)
摘要: 卡特兰数 阅读全文
posted @ 2026-05-10 00:17 qwynick 阅读(4) 评论(0) 推荐(0)
摘要: 卢卡斯定理是说 \(\binom{n}{m}=\binom{\lfloor n/p \rfloor}{\lfloor m/p \rfloor}\binom{n\%p}{m\%p} \pmod p\) 用起来简单,证明比较麻烦。 设 \(n=ap+b(0\le b<p)\)。 这里 \(a=\lflo 阅读全文
posted @ 2026-05-09 22:20 qwynick 阅读(2) 评论(0) 推荐(0)
摘要: 普通的积分一般把区间 \(l\sim r\) 区间的函数值处理成 \(f(\frac{l+r}{2})\),面积近似为 \(f(\frac{l+r}{2})(r-l)\)。 但是实践发现,直线的近似不如二次函数,辛普森积分即是采用二次函数逼近: 设中点 \(m=\frac{l+r}2 \rarr 4 阅读全文
posted @ 2026-05-09 19:32 qwynick 阅读(4) 评论(0) 推荐(0)
摘要: 一维偏序:直接排序看自己位置即可。 二维偏序:按第一维排序,之后归并排序或者树状数组求第二维偏序即可。 https://www.luogu.com.cn/problem/P3810 三维偏序:先按第一维排序,然后对数据进行分治处理。 由于第一维已经排好序,所以每次将区间分为两半的时候,左边的第一维一 阅读全文
posted @ 2026-05-09 18:56 qwynick 阅读(4) 评论(0) 推荐(0)
摘要: 莫队主要用于离线区间信息统计。 例子:有一个长度为 \(N(10^5)\) 的数组,数组每个位置有一个数值,需要做 \(Q(10^5)\) 次查询,每次查询给出一个区间 \([l,r]\),问区间内有多少个不同的数字出现特定的次数。 暴力极限是 \(O(NQ)\) 复杂度。 在暴力查询中,每次都要硬 阅读全文
posted @ 2026-05-09 17:51 qwynick 阅读(3) 评论(0) 推荐(0)
摘要: Nim与SG函数 有多堆石子,每次可以从一堆石子中拿任意多个,谁不能拿谁就输了,问必胜策略。 结论:只需要将所有石子求异或和,非 \(0\) 即有必胜策略。 证明:只要目前异或和 \(s\) 不为 \(0\),假定 \(s\) 最高非零位为第 \(b\) 位,只要某堆石子数量为 \(t\),且 \( 阅读全文
posted @ 2026-05-09 15:58 qwynick 阅读(2) 评论(0) 推荐(0)
摘要: 欧几里得算法,辗转除法: 要求 \(m\) 和 \(n\) 的最大公约数。 假定最大公约数为 \(g\),即有 \(g|n\) 且 \(g|m\)。 显然 \(g|n-m\)。 所以 \((n,m)=(n-m,m)=(n-2m,m)=(n-3m,m)...\) 所以可以直接一步到位 \((n,m)= 阅读全文
posted @ 2026-05-08 14:02 qwynick 阅读(4) 评论(0) 推荐(0)