__故人__

随笔

CF(8) UOJ(1) 每日一题(3) 牛客小白月赛27(10) 算法模板(10) 题解(117)

/ 注册

全部文章 / 随笔（共20篇）

后缀自动机从理解到实践

施工中。。后缀自动机 (suffix automaton, SAM) SAM 的概述可以解决很多字符串问题的强大工具。是一个可以处理字符串 SSS 的所有后缀的最小的确定性有限自动机。 SAM 的定义 SAM 是一张有向无环图。结点被称作状态，边被称作状态间的转移。图存在一个源点...

C++ 字符串

2022-06-21

3 632

任意模数多项式乘法来自专栏

任意模数多项式乘法 NTT 因为任意模数多项式乘法的系数可能超过了所以一般的就做不了。所以对于的做法是找到个模数，最后使用合并一下，但是这里的合并中的答案可能超过的值域，所以要用快速乘实现。 FFT 任意模数多项式乘法用实现的问题主要是因为精度问题，这里使用了次变化的...

2020-10-31

3 984

k阶差分与前缀和来自专栏

K阶前缀和这是我们对前缀和的定义。而阶前缀和就是把这个过程进行次。那么考虑卷积。其实可以看作而。是一个所有项都为的函数。那么。由于卷积是有结合率的，所有阶前缀和等同于。而对于的计算，可以采用多项式快速幂，但没必要。我们有生成函数，那么的生成函数...

2020-10-29

5 1707

[APIO2014]连珠线

写在前面的这是我不想做第二次的题目。分析我们什么都不说了，直接定义状态表示节点是否作为蓝线的中点的最优解。那么我们通过分析，一条蓝边一定是的路径。所以先考虑的暴力树形。和，然后就写好了。 #include<bits/stdc++.h> int re...

2020-10-26

5 680

第二类斯特林数·行来自专栏

推式子那么就转化为一个卷积形式。那么。用优化一下，就变为了。代码 #include<bits/stdc++.h> using namespace std; const int N = 8e5 + 100,mod = 167772161; int read() {in...

2020-10-24

4 572

关于通配符的单模式串匹配来自专栏

引入给你两个字符串。询问是否匹配。其中含有通配符。可以匹配任意一种字符。分析如果我们使用最常见的字符串匹配算法我们发现，对于的处理是非常复杂度的。这个我们引入一个函数。叫做字符串的距离函数。那么我们定义。这样如果我们把看做完全匹配的话，如果 ...

2020-10-18

2 705

多项式开根号来自专栏

引入求出多项式是满足系数对一个数取模。推导还是利用牛顿迭代。那么代入牛顿迭代的公式为然后没有学习过牛顿迭代的朋友可以看我上一篇。当然这下面这份代码不能解决的情况。那个时候应该使用二次剩余。代码 #include<bits/stdc++.h> using ...

2020-10-16

3 975

多项式快速幂来自专栏

引入求出满足的多项式。做法既然可以快速幂求，其实多项式也是可以的。那么总的复杂度为其实这个好写，常数也小，一般不会被卡。我们可以对一个多项式求和。那么求出。之后在做一次就可以了。记住，如果下面给出的代码并不能通过。代码 #include<...

2020-10-15

5 1087

多项式exp 来自专栏

引入求解系数对一个数取模。前置知识泰勒展开，这个相信学习过高数的朋友都知道。牛顿迭代，我们可以通过牛顿迭代找出一个函数的零点，当然这个是有一定限制的，这个可以百度搜一下。换句话就是已知，要求求出满足的多项式。考虑倍增，如果我们已经知道。那么根据泰勒展开因为的...

2020-10-15

4 647

多项式求ln 来自专栏

关于多项式的操作，我会慢慢补充的。多项式求ln 前置公式，和。前置知识，多项式点值表示，多项式求逆。给你一个多项式，要求求出一个多项式满足。考虑积分和求导。我们考虑是和复合。那么那么，左右同时积分。那么就做完了。代码 #include<b...

2020-10-13

4 611