avatar
文章
67
标签
78
分类
29
主页
关于
标签
分类
归档
Cauphenuny's Blog
搜索
主页
关于
标签
分类
归档

Cauphenuny's Blog

快速沃尔什变换
发表于2021-03-22|更新于2023-08-02|oi学习笔记数学多项式|FWT
快速沃尔什变换也许是快速地求位运算卷积的一种方法。 给定序列 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...
二次剩余 原根
发表于2021-03-16|更新于2023-08-02|oi数学数论|数论
改题,然后发现需要填填坑。 其实学起来也没有那么难。
20210225 考试总结
发表于2021-02-26|更新于2023-08-02|oi考试总结
Review 爆炸了,毒瘤出题人一场比赛 3 个数学题 solution 题还没有改完 其实是开学了要补作业
20210224 考试总结
发表于2021-02-24|更新于2023-08-02|oi考试总结
改题进度 [ ] T1 [x] T2 [ ] T3 学习进度 [x] 圆反演 [ ] 二次剩余 [ ] NTT [ ] 莫比乌斯反演 [x] Pollard-Rho
圆反演变换
发表于2021-02-24|更新于2023-08-02|oi学习笔记计算几何|计算几何•圆反演
定义 给定反演中心点 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)...
一些有用的小模板
发表于2021-02-23|更新于2023-11-18|oi模板|模板
树状数组 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 考试总结
发表于2021-02-23|更新于2023-08-02|oi考试总结|欧拉公式•分块•三元环计数•四元环计数•三角剖分•期望
改题进度 [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
发表于2021-02-22|更新于2023-08-02|oi
d8bb691c3eda980fd06150c71a35dc83c34e3376450b9ec0a70aace687932e57430c4d5d5e624d946e5b8852f5289ee9 这里需要密码
线性代数有关内容
发表于2021-02-21|更新于2023-08-02|oi学习笔记数学线性代数|数学•线性代数•矩阵•伴随矩阵•行列式
感谢来自 zxyhymzg 的线代小课堂(
分散层叠算法
发表于2021-02-21|更新于2023-08-02|oi学习笔记|科技
分散层叠用于解决以下问题: 给定总长度为 nnn 的 kkk 个序列,每次询问数 xxx 在每个序列中的非严格后继。 咕咕咕
1234…7
avatar
Cauphenuny
文章
67
标签
78
分类
29
Follow Me
最新文章
Basics of Diffusion2025-05-03
计组实验笔记2025-04-11
在 arm host 上使用 gdb 调试 amd64 程序2025-04-08
brainfuck 代码生成工具 - 将C代码编译到brainfuck2024-11-22
给C++实现一个模式匹配2024-11-08
最新评论
加载中...
分类
  • CS6
    • cpp2
    • env1
    • 编译原理1
    • 计科导2
  • oi50
    • 学习笔记18
      • dp2
标签
JavaScript 圆反演 编译原理 gdb 计算几何 欧拉公式 bitset 数学 poly env 树的重心 图论 三角剖分 四边形不等式 clang 分块 平衡树 凸壳 SAM 区间dp vim FWT 线段树 三元环计数 数学分析 软链接 C HNOI2021 Mac 数据结构 CS Bézout定理 树形dp 卷积 换根 dp 莫比乌斯反演 脚本 势能分析 brainfuck C++
归档
  • 五月 2025 1
  • 四月 2025 2
  • 十一月 2024 2
  • 七月 2024 1
  • 六月 2024 1
  • 四月 2024 3
  • 一月 2024 2
  • 十二月 2023 2
网站信息
文章数目 :
67
本站总字数 :
84k
本站访客数 :
本站总浏览量 :
最后更新时间 :
©2020 - 2025 By Cauphenuny
框架 Hexo|主题 Butterfly
搜索
数据加载中