Cauphenuny's Blog

改题进度 [ ] 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 的线代小课堂（

分散层叠用于解决以下问题： 给定总长度为 nnn 的 kkk 个序列，每次询问数 xxx 在每个序列中的非严格后继。 咕咕咕

Review 考试时一直在肝论文，发现 2017 国集论文里面有决策单调性优化 dp 的内容，终于在考试最后 2 分钟调过样例。 结果因为没有滚数组导致 MLE，沦为暴力 20pts。 Solution T1 hike nnn 个点， qqq 个询问 两种询问，分别是合并两树和查询树中里给定点最远的点的距离 LCT 维护树的直径板子题 O(nlog⁡n)O(n\log n)O(nlogn)，可惜我不会，只好启发式合并暴力处理倍增数组。 考虑两颗树的直径端点 a,b,c,da,b,c,da,b,c,d ，则合并出的新树直径只有可能是这 4 个数中的 2...

二分图的结论和算法 防止忘记 匈牙利算法的过程是，枚举每一个左部点 uuu ，然后枚举该左部点连出的边，对于一个出点 vvv，如果它没有被先前的左部点匹配，那么直接将 uuu 匹配 vvv，否则尝试让 vvv 的“原配”左部点去匹配其他右部点，如果“原配”匹配到了其他点，那么将 uuu 匹配 vvv，否则 uuu 失配。 二分图最大独立集等于总点数减去最大匹配

Index Review 考的不错，主要是第一题做出来了，分数可观， 140pts。 但是后面两题的暴力分也没有打满，这是做的不够的一点。 Solution pk 定义 f(n,k)=(n−k+1)!∑i=0k−1(n−ki)(kj−i−1)f(n,k)=(n-k+1)!\sum_{i=0}^{k-1}\dbinom{n-k}{i}\dbinom{k}{j-i-1}f(n,k)=(n−k+1)!∑i=0k−1​(in−k​)(j−i−1k​) ，求 ∑i=LRf(i+s,i)\sum\limits_{i=L}^{R}f(i+s,i)i=L∑R​f(i+s,i) 经过打表可以发现 f(n,n)=nf(n,n)=nf(n,n)=n 和 f(n,k)=f(n,k+1)⋅kf(n,k)=f(n,k+1)\cdot kf(n,k)=f(n,k+1)⋅k 化简得 f(n,k)=n!(k−1)!f(n,k)=\dfrac{n!}{(k-1)!}f(n,k)=(k−1)!n!​ type=1 首先考虑 type=1 的情况，代入式子即得...