qwynick

2026年5月10日

LGV引理

摘要： 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)

2026年5月9日

卢卡斯定理

摘要：卢卡斯定理是说 \(\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)

CDQ分治

摘要：一维偏序：直接排序看自己位置即可。二维偏序：按第一维排序，之后归并排序或者树状数组求第二维偏序即可。 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函数

摘要： Nim与SG函数有多堆石子，每次可以从一堆石子中拿任意多个，谁不能拿谁就输了，问必胜策略。结论：只需要将所有石子求异或和，非 \(0\) 即有必胜策略。证明：只要目前异或和 \(s\) 不为 \(0\)，假定 \(s\) 最高非零位为第 \(b\) 位，只要某堆石子数量为 \(t\)，且 \( 阅读全文

posted @ 2026-05-09 15:58 qwynick 阅读(2) 评论(0) 推荐(0)

2026年5月8日

扩展欧几里得、中国剩余定理

摘要：欧几里得算法，辗转除法：要求 \(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)

公告