Cauphenuny's Blog

乘法 NTT 构造模意义单位根。 发现 δpgk=(p−1)gcd⁡(k,p−1)\delta_pg^k=\dfrac{(p-1)}{\gcd(k, p -1)}δp​gk=gcd(k,p−1)(p−1)​，当 n∣(p−1)n|(p-1)n∣(p−1) 时， δpg(p−1)/n=(p−1)gcd⁡(p−1n,p−1)=n\delta_pg^{(p-1)/n}=\dfrac{(p-1)}{\gcd(\frac{p-1}{n}, p-1)}=nδp​g(p−1)/n=gcd(np−1​,p−1)(p−1)​=n 令 ωn=g(p−1)/n\omega_n=g^{(p-1)/n}ωn​=g(p−1)/n ，则 ωn0,ωn1,⋯ ,ωnn−1\omega_n^0,\omega_n^1,\cdots,\omega_n^{n-1}ωn0​,ωn1​,⋯,ωnn−1​...

快速沃尔什变换也许是快速地求位运算卷积的一种方法。 给定序列 AAA 和 BBB ，求 CCC，满足 ci=∑i=j⊕kajbkc_i=\sum\limits_{i=j\oplus k}a_jb_kci​=i=j⊕k∑​aj​bk​，其中 ⊕\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(nlog⁡n)O(n\log n)O(nlogn) — O(n)O(n)O(n) — O(nlog⁡n)O(n\log...

改题，然后发现需要填填坑。 其实学起来也没有那么难。

Review 爆炸了，毒瘤出题人一场比赛 3 个数学题 solution 题还没有改完 其实是开学了要补作业

改题进度 [ ] 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...

改题进度 [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 。 期望即为...

d8bb691c3eda980fd06150c71a35dc83c34e3376450b9ec0a70aace687932e57430c4d5d5e624d946e5b8852f5289ee9 这里需要密码

感谢来自 zxyhymzg 的线代小课堂（