__故人__
__故人__
全部文章
随笔
CF(8)
UOJ(1)
每日一题(3)
牛客小白月赛27(10)
算法模板(10)
题解(117)
归档
标签
去牛客网
登录
/
注册
__故人__的博客
我太菜了/kk
全部文章
/ 随笔
(共20篇)
后缀自动机从理解到实践
施工中。。 后缀自动机 (suffix automaton, SAM) SAM 的概述 可以解决很多字符串问题的强大工具。是一个可以处理字符串 SSS 的所有后缀的 最小的 确定性有限自动机。 SAM 的定义 SAM 是一张有向无环图。结点被称作 状态 ,边被称作状态间的 转移 。 图存在一个源点...
C++
字符串
2022-06-21
3
645
任意模数多项式乘法
来自专栏
任意模数多项式乘法 NTT 因为任意模数多项式乘法的系数可能超过了 所以一般的 就做不了。所以对于 的做法是找到 个模数,最后使用 合并一下,但是这里的合并中的答案可能超过 的值域,所以要用快速乘实现。 FFT 任意模数多项式乘法用 实现的问题主要是因为精度问题,这里使用了 次变化的...
2020-10-31
3
995
k阶差分与前缀和
来自专栏
K阶前缀和 这是我们对前缀和的定义。而 阶前缀和就是把这个过程进行 次。那么考虑卷积。 其实可以看作 而 。 是一个所有项都为 的函数。那么 。由于卷积是有结合率的,所有 阶前缀和等同于 。而对于 的计算,可以采用多项式快速幂,但没必要。我们有生成函数 ,那么 的生成函数...
2020-10-29
5
1758
[APIO2014]连珠线
写在前面的 这是我不想做第二次的题目。 分析 我们什么都不说了,直接定义状态 表示 节点是否作为蓝线的中点的最优解。那么我们通过分析,一条蓝边一定是 的路径。所以先考虑 的暴力树形 。 和 ,然后 就写好了。 #include<bits/stdc++.h> int re...
2020-10-26
5
690
第二类斯特林数·行
来自专栏
推式子 那么就转化为一个卷积形式 。那么 。用 优化一下,就变为 了。 代码 #include<bits/stdc++.h> using namespace std; const int N = 8e5 + 100,mod = 167772161; int read() {in...
2020-10-24
4
580
关于通配符的单模式串匹配
来自专栏
引入 给你两个字符串 。询问 是否匹配。其中 含有通配符 。 可以匹配任意一种字符。 分析 如果我们使用最常见的字符串匹配算法 我们发现,对于 的处理是非常复杂度的。这个我们引入一个函数 。叫做字符串 的距离函数。那么我们定义 。这样如果我们把 看做完全匹配的话,如果 ...
2020-10-18
2
720
多项式开根号
来自专栏
引入 求出多项式是 满足 系数对一个数取模。 推导 还是利用牛顿迭代 。那么代入牛顿迭代的公式为 然后没有学习过牛顿迭代的朋友可以看我上一篇。 当然这下面这份代码不能解决 的情况。那个时候应该使用二次剩余。 代码 #include<bits/stdc++.h> using ...
2020-10-16
3
993
多项式快速幂
来自专栏
引入 求出满足 的多项式 。 做法 既然可以快速幂求 ,其实多项式也是可以的。那么总的复杂度为 其实这个好写,常数也小,一般不会被卡。 我们可以对一个多项式求 和 。那么 求出 。之后在做一次 就可以了。记住,如果 下面给出的代码并不能通过。 代码 #include<...
2020-10-15
5
1102
多项式exp
来自专栏
引入 求解 系数对一个数取模 。 前置知识 泰勒展开, 这个相信学习过高数的朋友都知道。 牛顿迭代,我们可以通过牛顿迭代找出一个函数的零点,当然这个是有一定限制的,这个可以百度搜一下。换句话就是已知 ,要求求出满足 的多项式 。考虑倍增,如果我们已经知道 。那么根据泰勒展开 因为 的...
2020-10-15
4
658
多项式求ln
来自专栏
关于多项式的操作,我会慢慢补充的。 多项式求ln 前置公式, 和 。 前置知识,多项式点值表示,多项式求逆。 给你一个多项式 ,要求求出一个多项式满足 。考虑积分和求导。我们考虑 是 和 复合。那么 那么 ,左右同时积分 。那么就做完了。 代码 #include<b...
2020-10-13
4
626
首页
上一页
1
2
下一页
末页