https://wiki.cvbbacm.com/ 2026-04-30T13:34:43+0800 https://wiki.cvbbacm.com/ https://wiki.cvbbacm.com/lib/exe/fetch.php?media=favicon.ico text/html 2021-09-14T10:43:02+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:%E7%8E%8B%E6%99%BA%E5%BD%AA:%E5%8D%9A%E5%BC%88%E8%AE%BA%E6%96%B0%E6%80%BB%E7%BB%93&rev=1631587382&do=diff 博弈论新总结 公平组合游戏 需要满足的三个条件： 1.由两名玩家交替行动 2.在游戏进程的任意时刻，可以执行的合法行动与轮到哪名玩家无关 3.游戏中的同一个状态不可能多次抵达，游戏以玩家无法行动为结束，且游戏一定会在优先步后以非平局结束。$O(n+m)$$n$$m$$a,b$${\frac 1 a}+{\frac 1 b}=1$$A,B$$A={\lfloor {na} \rfloor},B={\lfloor {nb} \rfloor},n∈Z$$A∩B=∅,A∪B=N^{+}$$10^{100}$${\lfloor {\frac {(b-a)×({\sqrt {5}}+1)} {2}} \rfloor}==a$$Java$${\sqrt {5}}$… text/html 2021-09-14T11:20:28+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:%E7%8E%8B%E6%99%BA%E5%BD%AA:%E5%8D%9A%E5%BC%88%E8%AE%BA&rev=1631589628&do=diff 博弈论 博弈图 定理1：没有后继状态的状态是必败状态 定理2：一个状态是必胜状态当且仅当存在至少一个必败状态为它的后继状态 定理3：一个状态是必败状态当且仅当它的所有后继状态均为必胜状态$O(N+M)$$N$$M$$nim$$0$$0$$0$$0$$0$$t$$t$$1$$0$$t$$1$$a_{i}$$a_{i}'=a_{i}$$t$$mex$$S$$x$$k$$y_{1},y_{2},…,y_{k}$$SG$$SG(x)=mex\{SG(y_{1}),SG(y_{2}),…,SG(y_{k})\}$$SG$$0$$n$$s_{1},s_{2},…,s_{n}$$SG(s_{1})$$SG(s_{2})$$…$$SG(s_{n})≠0$$x$$SG$$nim$$0$$SG(x)=x$$Anti-SG$$Anti-SG$$SG$$0$$1$$1$$0$$1$$1$$0$$0$$0$$0$$1$$1$$0$$0$$1$$1$$0$$1$$2$$1$$2$$Anti-SG$$SG$$0$$SG$$0$$SG$$1$$Anti-Nim$$1$$1$$0$$SG$$0$$SG$$1$$… text/html 2021-08-06T18:33:00+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:%E7%8E%8B%E6%99%BA%E5%BD%AA:%E5%8F%8D%E6%BC%94&rev=1628245980&do=diff 反演变换 算法思想 给定反演中心 $O$ 和反演半径 $r$ ，剩余点 $A$ 的反演点 $A'$ 满足 $|OA|×|OA'|=R^{2}$ 。 可以发现不过 $O$ 的圆 $B$ ，其反演图形也是不过 $O$ 的圆 $B'$ 。 圆 $A$ 半径为 $r_{1}$ ，其反演图形的半径为 ${\frac 1 2}({\frac 1 {|OA|-r_{1}}}-{\frac 1 {|OA|+r_{1}}})R^{2}$ 。 设 $O$ 点坐标为 $(x_{0},y_{0})$$A$$(x_{1},y_{1})$$B$$x_{2}=x_{0}+{\frac {|OB|} {|OA|}}(x_{1}-x_{0})$$y_{2}=y_{0}+{\frac {|OB|} {|OA|}}(y_{1}-y_{0})$$|OB|$$O$$A$$O$$O$… text/html 2021-08-01T22:28:26+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:%E7%8E%8B%E6%99%BA%E5%BD%AA:%E5%9B%9E%E6%96%87%E8%87%AA%E5%8A%A8%E6%9C%BA&rev=1627828106&do=diff 回文自动机（姬） 算法思想 回文自动机是一种可以存储一个串中所有回文子串的数据结构。 与其他自动机类似，回文自动机也有转移边和失配指针 $fail$ 组成，每个结点都代表一个回文子串。$fail$$len$$-1,0$$fail$$fail$$p-1$$p$$fail$$s_{p}=s_{p-len-1}$$len$$-1$$s_{p}=s_{p}$$fail$$fail$$fail$$fail$$0$$s$$|s|$$O(|s|)$$-2$$tot-1$$cnt$$AC$$fail$$fail$$s(1≤|s|≤10^{5})$$k$$s_{1},…,s_{k}$$s$$dp$$dp[i]$$s$$i$$i$$dp[i]=1+min_{s[j+1]…i ok}(dp[j])$$O(n^{2})$$O(n^{2})$$s$$t$$border$$border$$t$$s$$border$$|s|-|t|$$s$$t$$s$$t$$s$$border$$t$$t$$s$$border(|s|≤2|t|)$$s$$t$$s$$t$$t$$t$$s$$border$$|s|-|t|$$… text/html 2021-07-16T13:38:46+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:%E7%8E%8B%E6%99%BA%E5%BD%AA:%E5%90%8E%E7%BC%80%E5%B9%B3%E8%A1%A1%E6%A0%91&rev=1626413926&do=diff 后缀平衡树 算法简介&算法实现 前置芝士：平衡树 这里用 $Treap$ $Treap=BST+Heap$ $Heap$ 的结构是一定的， $BST$ 按照同一种规则建的树的中序遍历也是一定的。 $val$ 遵循 $BST$ ，$rnd$ 遵循 $Heap$ 。所以只要确定根节点， $Treap$ 的结构就是确定的，根据 $rnd$$val$$rnd$$val$$rnd$$log_{n}$$1$$1$$val$$cmp$$cmp$$l$$r$$(l+r)/2$$l$$(l+r)/2-1$$(l+r)/2+1$$r$$O(logn)$$double$$FHQ Treap$$O(logn)$$sa, rk, height$$sa$$i$$rk$$i$$height$$i-1$$i$$LCP$$dfs$$sa$$rk$$O(logn)$$n$$O(nlogn)$$n$$O(n)$$n$$2$$n$$n$$2$$n$$i$$i$$val$$init$$ADD$$s$$QUERY$$mask$$0$$mask$$mask$$|init|≤6×10^{5},Q≤6×10^{5}$$≤… text/html 2021-07-28T15:53:23+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:%E7%8E%8B%E6%99%BA%E5%BD%AA:%E5%90%8E%E7%BC%80%E6%95%B0%E7%BB%84&rev=1627458803&do=diff 后缀数组 算法思想 后缀数组有两个数组 $sa$ 和 $rk$ 。 $sa[i]$ 表示将所有后缀排序后第 $i$ 小的后缀的编号， $rk[i]$ 表示后缀 $i$ 的排名。 所以显然 $sa[rk[i]]=rk[sa[i]]=i$ 。 显然暴力排序求这俩数组的做法是 $n^{2}logn$ 的。 有一个倍增算法，是利用上一次前和后两个段的排序名次作为第一第二关键字，进行新的一轮排序，这样需要排序 $logn$$sort$$nlogn$$nlog^{2}n$$O(n)$$O(nlogn)$$height$$lcp(sa[i],sa[i-1])$$lcp$$height[rk[i]]≥height[rk[i-1]]-1$$height$$O(n)$$lcp(sa[i],sa[j])=min\{height[i+1……j]\}$$A=S[a……b],B=S[c……d]$$lcp(a,c)≥min(|A|,|B|)$$A<B$$|A|<|B|$$A<B$$rk[a]<rk[c]$${\frac {n(n+1)} 2}$$lcp$$lcp$${\frac {n(n+1)} 2}-… text/html 2021-07-30T17:04:15+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:%E7%8E%8B%E6%99%BA%E5%BD%AA:%E5%90%8E%E7%BC%80%E8%87%AA%E5%8A%A8%E6%9C%BA&rev=1627635855&do=diff 后缀自动机（姬） 算法思想 后缀自动机简称 $SAM$ 。 我们记 $\sum$ 为字符集， $|\sum|$ 为字符集大小。 以下问题可以通过 $SAM$ 在线性时间内解决。 1.在另一个字符串中搜索一个字符串的所有出现位置。（ $kmp$ 、哈希也可以）$SAM$$n$$SAM$$O(n)$$SAM$$O(n)$$SAM$$2n-1$$3n-4$$endpos$$s$$t$$endpos(t)$$s$$t$$0$$abcbc$$endpos("bc")=2,4$$t_{1}$$t_{2}$$endpos$$c$$bc$$endpos$$s$$SAM$$endpos$$SAM$$+1$$s$$u$$v$$endpos$$endpos$$link(v)$$v$$t_{0}$$v_{0}$$t_{0}$$[minlen(v_{i}),len(v_{i})]$$ [0,len(v_{0})]$$SAM$$len$$link$$SAM$$t_{0}$$0$$t_{0}$$len=0,link=-1$$-1$$last$$c$$cur$$len(cur)$$len(last)+1$$… text/html 2021-07-20T21:35:31+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:%E7%8E%8B%E6%99%BA%E5%BD%AA:%E5%A4%9A%E9%A1%B9%E5%BC%8F%E6%B1%82%E9%80%86&rev=1626788131&do=diff 多项式求逆 准备工作 void calc_rev(int &n,int &lim,const int m) { n = 1,lim = 0; while(n < m) n <<= 1,lim++; for(int i = 1; i < n; i++) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << lim - 1); } 递归复杂度 $O(nlogn)$ void Inv(const int *a,int *b,const int len) { //多项式求逆 static int c[N]; if(len == 1) { b[0] = qpow(a[0],mod - 2); return; } Inv(a,b,len + 1 >> 1); int n,lim; calc_rev(n,lim,len << 1); for(int i = 0; i < n; i++) c[i] = a[i]; for(int i = len; i < n; i++) c[i] = 0; NTT(c,n,1),NTT(… text/html 2021-08-13T21:44:21+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:%E7%8E%8B%E6%99%BA%E5%BD%AA:%E5%B8%B8%E7%B3%BB%E6%95%B0%E9%BD%90%E6%AC%A1%E7%BA%BF%E6%80%A7%E9%80%92%E6%8E%A8&rev=1628862261&do=diff 常系数齐次线性递推 算法思想 求一个满足 $k$ 阶齐次线性递推数列 $a_{i}$ 的第 $n$ 项，即： $a_{n}=\sum_{i=1}^{k} f_{i}×a_{n-i}$ ，求 $a_{n}$ 。 其中 $n≤10^{9},k≤32000,|f_{i}|,|a_{0},…,a_{k-1}|≤10^{9}$ 解法是求用快速幂求 $x^{n}$ 对特征多项式 $p$ 取模的结果。 比如求斐波那契数列的第五项 $fib_{5}$ ，于是我们相当于 $0x^{0}+0x^{1}+…+1x^{5}$$x^{5}$$x^{4}$$x^{3}$$0x^{0}+0x^{1}+…+1x^{3}+1x^{4}+0x^{5}$$x^{2}-x-1$$x^{n}$$x_{k}-p_{1}x_{k-1}-p_{2}x_{k-1}-…-p_{k}$… text/html 2021-08-01T19:25:15+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:%E7%8E%8B%E6%99%BA%E5%BD%AA:%E5%BA%8F%E5%88%97%E8%87%AA%E5%8A%A8%E6%9C%BA&rev=1627817115&do=diff 序列自动机 算法思想 序列自动机是接受且仅接受一个字符串的子序列的自动机。字符串设为 $s$ 。 若 $s$ 包含 $n$ 个字符，那么序列自动机包括 $n+1$ 个状态。 令 $t$ 是 $s$ 的一个子序列，则 $d(start,t)$ 是 $t$ 在 $s$ 第一次出现时末端的位置。$i$$s[1…i]$$s[1…i-1]$$d(u,c)=min\{i|i>u,s[i]=c\}$$c$$i＞j$$s[i…|s|]$$s[j…|s|]$$O(n|\sum|)$$S$$q$$T$$T$$S$$len(S)≤10^{5},q≤10^{5},\sum len(T)≤10^{6}$$t_{0}$$O(len^{2})$$O(\sum |T|)$$O(len)$$upper_bound(pos[c].begin(),pos[c].end(),now_pos);$$end$$O(|S|+\sum |T|*log(|S|))$$vector$$O(logn)$$2000$$s_{1},s_{2}$$s_{1}$$s_{2}$$s_{1}$$s_{2}$$s_{1}$$s_{2}$$s_{… text/html 2021-08-04T11:52:28+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:%E7%8E%8B%E6%99%BA%E5%BD%AA:%E6%89%AB%E6%8F%8F%E7%BA%BF&rev=1628049148&do=diff 扫描线 算法思想 问题引入：给 $n$ 个矩形的左下角和右上角坐标 求并集覆盖的总面积 复杂度 $O(nlogn)$ 比如按照横坐标从左到右扫，横坐标小的为 $1$ ，横坐标大的为 $-1$ ，面积就是相邻横坐标的差乘以当前区间有多少覆盖是正数的（毕竟不可能是负数）。这个线段树维护一下就行了。遇到 $1$$-1$$update$$(×)$ text/html 2021-08-10T23:17:55+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:%E7%8E%8B%E6%99%BA%E5%BD%AA:%E6%95%B0%E7%90%86%E7%9F%A5%E8%AF%86&rev=1628608675&do=diff 数理知识总结 位运算 判断一个数是不是 $2$ 的非负整数次幂 bool isPowerOfTwo(int n) { return n>0&&(n&(n-1))==0; } 对2的非负整数次幂取模 $mod$ 代表 $2^{k}$ int modPowerOfTwo(int x,int mod) { return x&(mod-1); } 取绝对值 $n>0?n:-n$$a>b?a:b$$a>=b,(a-b)>>31$$0$$-1$$a\&(~b)$$a$$b$$O(2^{popcount(u)})$$u$$O(3^{n})$$x$$1$$1$$x$$0$$0$$x$$0$$1$$x$$1$$x$$1$$n$$p_{i}$$m$$k$$O(nmk)$$k$$3×3$$3×3$$1$$4×4$$AX=X'$$x'=x+dx$$X$$X'$$4×1$$1$$X$$X'$$1$$A$$1$$X'$$1$$1$$z$$z$$1$$2×2$$x,y$$k$$O(mlogk)$$n$$O(n+mlogk)$$1$$u,v$$u$$v$$k$$k$$k$$1$$n$… text/html 2021-09-25T19:16:27+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:%E7%8E%8B%E6%99%BA%E5%BD%AA:%E6%95%B0%E8%AE%BA&rev=1632568587&do=diff 数论 整除 如果 $k_{1},k_{2}$ 互质，则 $k_{1}+k_{2}$ 与 $k_{1}×k_{2}$ 互质。 在自然数集中，小于 $n$ 的质数约有 ${\frac {n} {ln(n)}}$ 个。 切比雪夫定理 $1.$ 对整数 $n＞3$ ，则至少存在一个质数 $p$ ，符合 $n＜p＜2n-2$ 。 $2.$ 对任意自然数 $n > 6$ ， 至少存在一个 $4k + 1$ 型和一个 $4k + 3$ 型素数 $p$$n < p < 2n$$3.$$k$$N$$n > N$$k$$p$$n < p < 2n$$Miller-Rabin$$O(klogn)$$k$$O(nlog_{10}log_{10}n)≈O(n)$$O(log_{10}n)$$O(log_{10}log_{10}n)$$[L,R]$$sqrt(R)$$L$$p$$p$$O(R-L+{\sqrt {R}})$$i$$i$$i×prime[j]$$i%prime[j]==0$$i$$prime[j]$$i$$break$$O(n)$$1~n$$n$$1…n$$n$$N≤2^{31}$$1…… text/html 2021-09-10T21:25:51+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:%E7%8E%8B%E6%99%BA%E5%BD%AA:%E6%96%B0%E8%AE%A1%E7%AE%97%E5%87%A0%E4%BD%95%E6%80%BB%E7%BB%93&rev=1631280351&do=diff 新计算几何总结 1.关于计算误差 少用三角函数、除法、开方、求幂、取对数。 比如能除一次不除三次： ${\frac {1.0} {2.0}}×{\frac {3.0} {4.0}}×5.0={\frac {1.0×3.0×5.0} {2.0×4.0}}$ 比较时在不溢出的情况下尽量将除法变为乘法： ${\frac a b}＞c \Leftrightarrow a＞bc$ 在不溢出整数范围的情况下，有时可以通过乘 $10^{k}$$-0$$acos(1.0000001)$$re$$fabs(a1-a2)<eps||fabs(a1-a2)>2.0*pi-eps$$atan2$$180$$2×pi$$atan2(0,0)=0,atan2(1,0)=pi/2,atan2(-1,0)=-pi/2,atan2(0,1)=0,atan2(0,-1)=pi$$atan2$$double\ tmp=atan2(a1);\ if(sgn(tmp)<0)\ tmp+=2*pi;$$[0,2×pi)$$a$$b$$a$$b$$M_{a}={\frac {sqrt(2(b^{2}+c^{2})-a^… text/html 2021-08-17T11:32:49+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:%E7%8E%8B%E6%99%BA%E5%BD%AA:%E7%B1%BB%E6%AC%A7%E5%87%A0%E9%87%8C%E5%BE%97%E7%AE%97%E6%B3%95&rev=1629171169&do=diff 类欧几里得算法 算法思想 我们设 $f(a,b,c,n)=\sum_{i=0}^{n}\lfloor {\frac {ai+b} {c}} \rfloor$ 其中 $a,b,c,n$ 为常数，我们需要一个 $O(logn)$ 的算法。 如果 $a≥c$ 或者 $b≥c$ ，我们可以将 $a,b$ 对 $c$ 取模来化简问题： $f(a,b,c,n)=\sum_{i=0}^{n}\lfloor {\frac {ai+b} {c}} \rfloor$ $=\sum_{i=0}^{n}\lfloor {\frac {(\lfloor {\frac a c} \rfloor c+a\ mod\ c)i+(\lfloor {\frac b c} \rfloor c+b\ mod\ c)} {c}} \rfloor$ $={\frac {n(n+1)} {2}}\lfloor {\frac a c} \rfloor+(n+1)\lfloor {\frac b c} \rfloor+\sum_{i=0}^{n}\lfloor {\frac {(a\ mod\ c)i+(b\ mod\ … text/html 2021-08-17T11:38:24+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:%E7%8E%8B%E6%99%BA%E5%BD%AA:%E7%BC%93%E5%86%B2%E5%8C%BA&rev=1629171504&do=diff 给一个凸多边形，和凸多边形外侧若干个点，每个点作为一盏灯，向四面八方发出光线，让用最少的点照亮平面除凸包内部外所有区域，如果不存在方案输出 $-1$ 。 我们注意到，一个点能照亮的最大区域是这个点对于这个凸包求左右两条切线，然后点亮所有区域的等价条件是所有边都被一个点的两条切线夹起来过。然后这个问题就转化为环形结构内给若干个线段（可以跨过原点），求最少的线段的数量，覆盖 $1$$n$… text/html 2021-07-15T18:26:38+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:%E7%8E%8B%E6%99%BA%E5%BD%AA:%E7%BD%91%E7%BB%9C%E6%B5%81%E5%85%A5%E9%97%A8&rev=1626344798&do=diff 网络流入门 算法简介 几个概念 容量 每条边$(u,v)$都有一个权值$c(u,v)$，被称为容量，而当边不属于这个图时，容量为0 流 流满足以下几个条件： 容量限制：流经过边的流量不能超过该边的容量，即 $f(u,v)≤c(u,v)$$f(u,v)=-f(v,u)$$c_{f}(u,v)=c(u,v)-f(u,v)$$f$$G_{f}$$G$$0$$EK,Dinic,SAP,ISAP$$n$$m$$BFS$$BFS$$O(nm^{2})$$0$$O(n^{2}m)$$EK$$EK$$O(m\sqrt{n})$$Dinic$$BFS$$t$$s$$BFS$$Dinic$$1$$ISAP$$i$$d_{i}$$i$$j$$d_{i}=d_{j}+1$$d_{i}=n$$d_{s}≥n$$ISAP$$GAP$$i$$num[i]$$x$$y$$num$$num[x]==0$$d_{s}$$n$$Dinic$$Dinic$$s$$t$$1$$s$$s$$s$$n$$t$$s$$BFS$$s$$BFS$$GAP$$ISAP$$n+1$$s$$O(n^{2}\sqrt{m})$$I… text/html 2021-07-24T11:14:24+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:%E7%8E%8B%E6%99%BA%E5%BD%AA:ac%E8%87%AA%E5%8A%A8%E6%9C%BA&rev=1627096464&do=diff AC自动机 算法思想 $AC$ 自动机 $=TRIE+KMP$ 所有的模式串构成一棵 $TRIE$ 。并在 $Trie$ 树上所有结点构造失配指针： $KMP$ 思想。 为了进行多模式匹配。 $Trie$ 构建操作和 $trie$ 的 $insert$ 的操作一模一样，其中每个结点代表某个字符串（也有可能是很多个）的某个前缀。$fail$$KMP$$KMP$$AC$$u$$fail$$v$$v$$u$$u$$u$$p$$p$$c$$u$$ch[p] [c]=u$$ch[fail[p]] [c]$$c$$c$$u$$fail$$ch[fail[p]] [c]$$ch[fail[p]] [c]$$fail$$ch[fail[fail[p]]] [c]$$fail$$fail$$build()$$fail$$BFS$$fail$$fail$$1$$1$$BFS$$fail$$p$$fail$$fail$$query()$$nownode$$fail$$tmpnode$$fail$$nownode$$trie$$O(\sum |s_{i}|+n|\sum|+|S|)$$n$$AC$$… text/html 2021-08-12T22:45:33+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:%E7%8E%8B%E6%99%BA%E5%BD%AA:exkmp&rev=1628779533&do=diff $exKMP$ 算法思想 $exKMP$ 可以求得模式串和文本串的后缀的最长公共前缀 $z$ 数组是自己的后缀和自己的最长公共前缀 $extend$ 数组是文本串的后缀和模式串的最长公共前缀 这里 $s$ 是文本串， $t$ 是模式串 text/html 2021-07-20T16:47:38+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:%E7%8E%8B%E6%99%BA%E5%BD%AA:fft&rev=1626770858&do=diff FFT 补充板子 #include<iostream> #include<cstdio> #include<cmath> #include <string.h> using namespace std; const int MAXN=4000100; const double Pi=acos(-1.0); struct complex { double x,y; complex (double xx=0,double yy=0) { x=xx,y=yy; } } a[MAXN],b[MAXN]; complex operator + (complex a,complex b) { return complex(a.x+b.x , a.y+b.y); } complex operator - (complex a,complex b) { return complex(a.x-b.x , a.y-b.y); } complex operator * (complex a,complex b) { return complex(a.x*b.x-a.y*b.y , a… text/html 2021-08-14T09:08:28+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:%E7%8E%8B%E6%99%BA%E5%BD%AA:fwt&rev=1628903308&do=diff FWT快速沃尔什变换 算法思想 或卷积 大概长这个样子： $C_{k} = \sum_{i|j=k} A_{i}×B_{j}$ 满足交换律、结合律 $(A+B)|C=A|C+B|C$ ，均为显然 几个重要的结论： $FWT(A+B) = FWT(A) + FWT(B)$ $FWT(A) = (FWT(A_{0}),FWT(A_{0})+FWT(A_{1}))$ ， $A_{0}$ 表示最高位为 $0$ 的部分，也就是前 $2^{n-1}$ 项； $A_{1}$ 表示最高位为 $1$ 的部分，也就是后 $2^{n-1}$$or$$FWT(A)[I] = \sum_{j|i=i}A[j]$$FWT(A|B)$$=FWT((A|B)_{0},(A|B)_{1})$$=FWT(A_{0}|B_{0},A_{0}|B_{1}+A_{1}|B_{0}+A_{1}|B_{1})$$=(FWT(A_{0}|B_{0}),FWT(A_{0}|B_{0}+A_{0}|B_{1}+A_{1}|B_{0}+A_{1}|B_{1}))$$=(FWT(A_{0})×FWT(B_{0}),FWT(A… text/html 2021-07-20T16:50:18+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:%E7%8E%8B%E6%99%BA%E5%BD%AA:ntt&rev=1626771018&do=diff NTT $1004535809$ 的原根是 $3$ 别算了（x 补充板子 #include<bits/stdc++.h> #define ll long long using namespace std; const ll maxn = 4e6+10; const ll inf = 1e9; const double eps = 1e-8; const ll mod = 998244353; ll f[maxn],g[maxn],mxn,w[maxn],n,m,rw[maxn],t[maxn],bit,pos[maxn],s[maxn],limit; inline ll quick_mul(ll a,ll b,ll p){ unsigned long long c=(long double) a/p*b; ll ret=a*b-(unsigned long long)c*p; ret%=p; while(ret<0) ret+=p; return ret%p; } inline ll quick_power(ll a,ll b,ll p){ ll ret…