快速沃尔什变换
快速沃尔什变换也许是快速地求位运算卷积的一种方法。 给定序列 AAA 和 BBB ,求 CCC,满足 ci=∑i=j⊕kajbkc_i=\sum\limits_{i=j\oplus k}a_jb_kci=i=j⊕k∑ajbk,其中 ⊕\oplus⊕ 是某种运算。 与 FFT 一样, FWT 有几个流程,先将 A,BA,BA,B 变换为 FWT(A),FWT(B)\operatorname{FWT}(A),\operatorname{FWT}(B)FWT(A),FWT(B),再计算 FWT(C)i=FWT(A)i×FWT(B)i\operatorname{FWT}(C)_i=\operatorname{FWT}(A)_i\times\operatorname{FWT}(B)_iFWT(C)i=FWT(A)i×FWT(B)i,最后将 FWT(C)\operatorname{FWT}(C)FWT(C) 转换回 CCC。 总之,是 O(nlogn)O(n\log n)O(nlogn) — O(n)O(n)O(n) — O(nlogn)O(n\log...
二次剩余 原根
改题,然后发现需要填填坑。 其实学起来也没有那么难。
20210225 考试总结
Review 爆炸了,毒瘤出题人一场比赛 3 个数学题 solution 题还没有改完 其实是开学了要补作业
20210224 考试总结
改题进度 [ ] T1 [x] T2 [ ] T3 学习进度 [x] 圆反演 [ ] 二次剩余 [ ] NTT [ ] 莫比乌斯反演 [x] Pollard-Rho
圆反演变换
定义 给定反演中心点 OOO 和反演半径 RRR 。若平面上点 PPP 和 P′P'P′ 满足: 点 P′P'P′ 在射线 OP→\overrightarrow{OP}OP 上 ∣OP∣⋅∣OP′∣=R2|OP| \cdot |OP'| = R^2∣OP∣⋅∣OP′∣=R2 则称点 PPP 和点 P′P'P′ 互为反演点。 下图所示即为平面上一点 PPP 的反演: 性质 圆 OOO 外的点的反演点在圆 OOO 内,反之亦然;圆 OOO 上的点的反演点为其自身。 不过点 OOO 的圆 AAA ,其反演图形也是不过点 OOO 的圆。 记圆 AAA 半径为 r1r_1r1 ,其反演图形圆 BBB 半径为 r2r_2r2 ,则有: r2=12(1∣OA∣−r1−1∣OA∣+r1)R2r_2 = \frac{1}{2}\left(\frac{1}{|OA| - r_1} - \frac{1}{|OA| + r_1}\right)...
一些有用的小模板
树状数组 bit.h 12345678//自定义类型需重载 + - 运算符template <typename T, int maxn>class binary_indexed_tree { T c[maxn + 10]; public: void add(int p, T v) { p++; for (; p <= maxn; p += p & -p) c[p] += v; } T query(int p) { p++; T v = 0; for (; p; p -= p & -p) v += c[p]; return v; } T range(int l, int r) { return query(r) - query(l - 1); }}; 可删堆 deletable_priority_queue.h 12345678910111213141516//自定义类型要求同 priority_queue 相同。template...
20210222 考试总结
改题进度 [x] forgive [x] palingenesis [x] destiny Review 人要有梦想,暴力还是要打的,没准就过了呢。 Solution T1 forgive 平面内 nnn 个点 (xi,yi)(x_i,y_i)(xi,yi),每个点有 ppp 的概率出现,保证三点不共线。可以在两个点之间连一条线段,线段之间不能相交,求最多可以连的线段数的期望。 考虑一个平面图,一定是三角剖分时连的线段最多。 对于一个三角剖分 我们想求的就是剖分的线段数。 设边数为 EEE ,点数为 VVV ,凸包上有 kkk 个点,FFF 个有界面,则有结论 E=3V−k−3E=3V-k-3E=3V−k−3 下面证明这个结论。 对于平面图,有欧拉公式 V+F−E=1V+F-E=1V+F−E=1 ,又有 2E=3F+k2E=3F+k2E=3F+k (三角形三条边,加上凸包上的边就都算了两次) 将两个式子做一些运算,即可得到 E=3V−k−3E=3V-k-3E=3V−k−3 。 期望即为...
出题 idea
d8bb691c3eda980fd06150c71a35dc83c34e3376450b9ec0a70aace687932e57430c4d5d5e624d946e5b8852f5289ee9 这里需要密码
线性代数有关内容
感谢来自 zxyhymzg 的线代小课堂(
分散层叠算法
分散层叠用于解决以下问题: 给定总长度为 nnn 的 kkk 个序列,每次询问数 xxx 在每个序列中的非严格后继。 咕咕咕