2020-2021:teams:legal_string:王智彪:博弈论新总结

Anonymous (anonymous@undisclosed.example.com) — 2021-09-14T10:43:02+0800

博弈论新总结公平组合游戏需要满足的三个条件： 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}}$…

2020-2021:teams:legal_string:王智彪:博弈论

Anonymous (anonymous@undisclosed.example.com) — 2021-09-14T11:20:28+0800

博弈论博弈图定理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$$…

2020-2021:teams:legal_string:王智彪:反演

Anonymous (anonymous@undisclosed.example.com) — 2021-08-06T18:33:00+0800

反演变换算法思想给定反演中心 $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$…

2020-2021:teams:legal_string:王智彪:回文自动机

Anonymous (anonymous@undisclosed.example.com) — 2021-08-01T22:28:26+0800

回文自动机（姬）算法思想回文自动机是一种可以存储一个串中所有回文子串的数据结构。与其他自动机类似，回文自动机也有转移边和失配指针 $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|$$…

2020-2021:teams:legal_string:王智彪:后缀平衡树

Anonymous (anonymous@undisclosed.example.com) — 2021-07-16T13:38:46+0800

后缀平衡树算法简介&算法实现前置芝士：平衡树这里用 $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}$$≤…

2020-2021:teams:legal_string:王智彪:后缀数组

Anonymous (anonymous@undisclosed.example.com) — 2021-07-28T15:53:23+0800

后缀数组算法思想后缀数组有两个数组 $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

2020-2021:teams:legal_string:王智彪:后缀自动机

Anonymous (anonymous@undisclosed.example.com) — 2021-07-30T17:04:15+0800

后缀自动机（姬）算法思想后缀自动机简称 $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$$…

2020-2021:teams:legal_string:王智彪:多项式求逆

Anonymous (anonymous@undisclosed.example.com) — 2021-07-20T21:35:31+0800

多项式求逆准备工作 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(…

2020-2021:teams:legal_string:王智彪:常系数齐次线性递推

Anonymous (anonymous@undisclosed.example.com) — 2021-08-13T21:44:21+0800

常系数齐次线性递推算法思想求一个满足 $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}$…

2020-2021:teams:legal_string:王智彪:序列自动机

Anonymous (anonymous@undisclosed.example.com) — 2021-08-01T19:25:15+0800

序列自动机算法思想序列自动机是接受且仅接受一个字符串的子序列的自动机。字符串设为 $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_{…

2020-2021:teams:legal_string:王智彪:扫描线

Anonymous (anonymous@undisclosed.example.com) — 2021-08-04T11:52:28+0800

扫描线算法思想问题引入：给 $n$ 个矩形的左下角和右上角坐标求并集覆盖的总面积复杂度 $O(nlogn)$ 比如按照横坐标从左到右扫，横坐标小的为 $1$ ，横坐标大的为 $-1$ ，面积就是相邻横坐标的差乘以当前区间有多少覆盖是正数的（毕竟不可能是负数）。这个线段树维护一下就行了。遇到 $1$$-1$$update$$(×)$

2020-2021:teams:legal_string:王智彪:数理知识

Anonymous (anonymous@undisclosed.example.com) — 2021-08-10T23:17:55+0800

数理知识总结位运算判断一个数是不是 $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$…

2020-2021:teams:legal_string:王智彪:数论

Anonymous (anonymous@undisclosed.example.com) — 2021-09-25T19:16:27+0800

数论整除如果 $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……

2020-2021:teams:legal_string:王智彪:新计算几何总结

Anonymous (anonymous@undisclosed.example.com) — 2021-09-10T21:25:51+0800

新计算几何总结 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)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^…

2020-2021:teams:legal_string:王智彪:类欧几里得算法

Anonymous (anonymous@undisclosed.example.com) — 2021-08-17T11:32:49+0800

类欧几里得算法算法思想我们设 $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\ …

2020-2021:teams:legal_string:王智彪:缓冲区

Anonymous (anonymous@undisclosed.example.com) — 2021-08-17T11:38:24+0800

给一个凸多边形，和凸多边形外侧若干个点，每个点作为一盏灯，向四面八方发出光线，让用最少的点照亮平面除凸包内部外所有区域，如果不存在方案输出 $-1$ 。我们注意到，一个点能照亮的最大区域是这个点对于这个凸包求左右两条切线，然后点亮所有区域的等价条件是所有边都被一个点的两条切线夹起来过。然后这个问题就转化为环形结构内给若干个线段（可以跨过原点），求最少的线段的数量，覆盖 $1$$n$…

2020-2021:teams:legal_string:王智彪:网络流入门

Anonymous (anonymous@undisclosed.example.com) — 2021-07-15T18:26:38+0800

网络流入门算法简介几个概念容量每条边$(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…

2020-2021:teams:legal_string:王智彪:ac自动机

Anonymous (anonymous@undisclosed.example.com) — 2021-07-24T11:14:24+0800

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$$…

2020-2021:teams:legal_string:王智彪:exkmp

Anonymous (anonymous@undisclosed.example.com) — 2021-08-12T22:45:33+0800

$exKMP$ 算法思想 $exKMP$ 可以求得模式串和文本串的后缀的最长公共前缀 $z$ 数组是自己的后缀和自己的最长公共前缀 $extend$ 数组是文本串的后缀和模式串的最长公共前缀这里 $s$ 是文本串， $t$ 是模式串

2020-2021:teams:legal_string:王智彪:fft

Anonymous (anonymous@undisclosed.example.com) — 2021-07-20T16:47:38+0800

FFT 补充板子 #include #include #include #include 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…

2020-2021:teams:legal_string:王智彪:fwt

Anonymous (anonymous@undisclosed.example.com) — 2021-08-14T09:08:28+0800

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…

2020-2021:teams:legal_string:王智彪:ntt

Anonymous (anonymous@undisclosed.example.com) — 2021-07-20T16:50:18+0800

NTT $1004535809$ 的原根是 $3$ 别算了（x 补充板子 #include #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…

CVBB ACM Team 2020-2021:teams:legal_string:王智彪