GoldenPotato137的小屋

FFT/NTT
FFT/NTT

[Luogu P3723] [AH2017/HNOI2017]礼物

题面 传送门:洛咕 Solution 调得我头大,我好菜啊 好吧,我们来颓柿子吧: 我们可以只旋转其中一个手环。对于亮度的问题,因为可以在两个串上增加亮度,我们也可以看做是可以为负数的。 所以说,我们可以假设我们旋转$B$串,上下要加上的亮度差为$p$,可以直接拍出一个最暴力的柿子: 设$f(x)$表示$B$串以$x$为开头的差异值,有: $f(x)=\sum_{i=0}^{x-1}(B[i]-A[i+n-x]+p)^2+\sum_{i=x}^{n-1}(B[i]-A[i-x]+p)^2$ 大力展开化简后有: $f…

2019年3月1日 0条评论 669点热度 0人点赞 GoldenPotato137 阅读全文
FFT/NTT

[Luogu P4173]残缺的字符串

题面 传送门:洛咕 Solution 这题我写得脑壳疼,我好菜啊 好吧,我们来说正题。 这题.....emmmmmmm 显然KMP类的字符串神仙算法在这里没法用了。 那咋搞啊(或者说这题和数学有半毛钱关系啊) 我们考虑把两个字符相同强行变为一个数学关系,怎么搞呢? 考虑这题是带通配符的,我们可以这样设: $C(x,y)=(A[x]-B[y])^2*A[x]*B[y]$ 因此,我们可以看出两个字符一样当且仅当$C(x,y)=0$ 因此,我们再设一个函数$P(x)$表示$B$串以第$x$项为结尾的长度为…

2019年3月1日 0条评论 590点热度 0人点赞 GoldenPotato137 阅读全文
FFT/NTT

[Luogu P3338] [ZJOI2014]力

题面 传送门: 洛咕 BZOJ Solution 写到脑壳疼,我好菜啊 我们来颓柿子吧 $F_j=\sum_{i<j}\frac{q_i*q_j}{(i-j)^2}-\sum_{i>j}\frac{q_i*q_j}{(i-j)^2}$ $q_j$与$i$没有半毛钱关系,提到外面去 $F_j=q_j*\sum_{i<j}\frac{q_i}{(i-j)^2}-q_j*\sum_{i>j}\frac{q_i}{(i-j)^2}$ 左右同时除以$q_j$ $E_j=\sum_{…

2019年3月1日 0条评论 642点热度 0人点赞 GoldenPotato137 阅读全文
FFT/NTT

快速傅里叶变换学习笔记(FFT)

什么是FFT FFT是用来快速计算两个多项式相乘的一种算法。 如果我们暴力计算两个多项式相乘,复杂度必然是$O(n^2)$的,而FFT可以将复杂度降至$O(nlogn)$ 如何FFT 要学习FFT,我们得先了解它的思想。 首先,我们得先了解如何表示一个多项式。显然,我们最传统的方法表示多项式就是表示它的系数就好。但是,如果我们用系数来计算两个多项式相乘,复杂度无论如何都是$O(n^2)$的。因此,我们引入点值表示法。 补充资料:什么是点值表示 设A(x)是一个n−1次多项式,那么把n个不同的x代入,会得到n个y。这…

2019年3月1日 0条评论 788点热度 0人点赞 GoldenPotato137 阅读全文

GoldenPotato137

LLer/ACMer/HITer/数院菜鸡/ECS折磨中

最近评论
hilaolu 发布于 1 年前(03月16日) 球球屑gp翻我展示一下ua屑屑
Guava 发布于 1 年前(11月30日) @GoldenPotato137 暂时是 guavaoj.tk
碱式碳酸希 发布于 1 年前(11月30日) 可以先不要告诉老师们吗(偷偷搞的
碱式碳酸希 发布于 2 年前(11月04日) %%%%Tql 请求搬运至NNEZ校内OJ公告中。 展示链接: 请在启天楼内网中访问! :razz:...
630分苦苦挣扎的菜鸡土豆 发布于 2 年前(05月01日) 肥肠抱歉,刚刚看见呢。 那个发送留言不能立刻看见源于我站挂了个腾讯云cdn,默认会返缓存的内容qwq...
分类
  • CDQ分治
  • DAG DP
  • DP+DP
  • FFT/NTT
  • Kruskal重构树
  • LCT
  • LUCAS
  • NNEZ
  • set
  • splay
  • 主席树
  • 二分/二分答案
  • 位运算
  • 倍增
  • 其他
  • 分块
  • 动态规划
  • 卷积
  • 反演
  • 同余
  • 后缀数组
  • 后缀自动机
  • 哈希
  • 图论
  • 圆方树
  • 堆
  • 多项式
  • 字符串
  • 学习笔记
  • 容斥
  • 容斥
  • 左偏树
  • 并查集
  • 数位DP
  • 数学
  • 数据结构
  • 整体二分
  • 斯特林数
  • 最小割
  • 最短路径
  • 未分类
  • 树套树
  • 树形DP
  • 模拟
  • 深度学习
  • 游记/自闭记/滚粗记
  • 点分治
  • 状压DP
  • 生涯纪录
  • 线段树
  • 组合数学
  • 缩点/强连通分量
  • 网格DP
  • 网络最大流
  • 网络流
  • 背包DP
  • 虚树
  • 贪心
  • 边双/点双
归档
  • 2022年1月
  • 2021年9月
  • 2021年3月
  • 2021年2月
  • 2019年11月
  • 2019年4月
  • 2019年3月
  • 2019年2月

COPYRIGHT © 2022 GoldenPotato137的小屋. ALL RIGHTS RESERVED.

Theme Kratos Made By Seaton Jiang

桂ICP备20002051号