https://wiki.cvbbacm.com/ 2026-04-30T02:18:55+0800 https://wiki.cvbbacm.com/ https://wiki.cvbbacm.com/lib/exe/fetch.php?media=favicon.ico text/html 2020-05-22T19:52:15+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:i_dont_know_png:potassium:connected_component&rev=1590148335&do=diff 连通分量 强连通分量 只有有向图才有这种定义，强连通分量中，点两两可达。 SCC 主要用于缩点，每一个点仅属于一个 SCC。缩点后是一个 DAG ，在建新图过程中需要注意两点不应属于同一 SCC 。$p\rightarrow q$ text/html 2020-05-22T20:09:59+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:i_dont_know_png:potassium:lgv_lemma&rev=1590149399&do=diff LGV Lemma 更完整的定义见OI-wiki，这里给出一个应用较多的狭义定义（即 $\omega(P)=1$ 的情况）。 设起始点集合为 $A=\{a_1,a_2,\ldots,a_n\}$ ，终止点集合为 $B=\{b_1,b_2,\ldots,b_n\}$ ，在一个起止点有唯一确定排列路径集的 DAG 上， $A\rightarrow B$ 的不相交路径集 $S$ 的个数可以用行列式 $\det(M)$$M$$${\begin{pmatrix}e(a_{1},b_{1})&e(a_{1},b_{2})&\cdots &e(a_{1},b_{n})\\e(a_{2},b_{1})&e(a_{2},b_{2})&\cdots &e(a_{2},b_{n})\\\vdots &\vdots &\ddots &\vdots \\e(a_{n},b_{1})&e(a_{n},b_{2})&\cdots &e(a_{n},b_{n})\end{pmatrix}}$$$n=2$$$\det(M)=e(a_1,b_1)e(a_2,b_2)-e(a_1,b_2)e(a_2,b_1)$$$S$… text/html 2020-05-24T19:59:13+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:i_dont_know_png:potassium:linear_programming&rev=1590321553&do=diff 线性规划 标准型 描述线性规划问题的常用和最直观形式是标准型。标准型包括以下三个部分： * 一个需要极大 / 极小化的线性函数： $$\sum_{i=1}^{n}x_ik_i$$ * 以下形式的问题约束： $$\left\{\begin{aligned} a_{11}x_1+a_{12}x_2+&\cdots +a_{1n}x_n\le b_1\\ a_{21}x_1+a_{22}x_2+&\cdots +a_{2n}x_n\le b_2\\ \ &\cdots\\ a_{m1}x_1+a_{m2}x_2+&\cdots +a_{mn}x_n\le b_m\\ \end{aligned}\right. $$ * 和非负变量：$$x_i\ge 0$$$1$$x$$p$$x$$1$$q$$x$$1$$p\rightarrow q$$0=0$$k$$m_s$$m_e$$x_i$$i$$x_i\in\{0,1\}$$x_i$$1$$-(s_i-e_i)$$$… text/html 2020-05-22T20:12:08+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:i_dont_know_png:potassium:lyndon&rev=1590149528&do=diff Lyndon 串 介绍 Lyndon 串是满足本身为所有循环移位中字典序严格最小的串。 性质：$u<v$ 均为 Lyndon 串，则 $uv$ 也为 Lyndon 串。 又由于单个字符是一个 Lyndon 串，可依靠这种思想进行合并。 Lyndon 分解：将字符串 $s$$s=s_1s_2s_3\ldots s_m$$s_i$$\forall 1\le i<n:s_i\ge s_{i+1}$$i,j,k$$[0\ldots i-1]$$[i\ldots k-1]$$t$$t$$v$$k$$j=k-len(t)$$s[k]=s[j]$$k=k+1,j=j+1$$s[k] > s[j]$$s[i\ldots k]$$k=k+1,j=i$$s[k]<s[j]$$t$$i$$v$$i$$nxt[i]$$(l,k)$$r=nxt[l]$$lcp(suf(l),suf(r))=0$$[l,r-1]$$lcp(suf(l),suf(r))>0$$len = r-l,tot=len\cdot\left\lfloor\dfrac{lcp+len}{len}\right\rfloor$$s[l\… text/html 2020-05-22T20:08:44+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:i_dont_know_png:potassium:math_theory_revision_1&rev=1590149324&do=diff 扩展欧几里得 即： $ax+by=1$ ，给定 $a,b$ ，求 $x,y$ 。 和欧几里得算法一样，辗转相除，每次更新外层 $x,y$ 对即可。 需要注意的是， $ax+by=c$ 有解当且仅当 $\gcd(a,b) |c$ ，需要进行特判。 原根 由欧拉定理，若 $(a,n)=1$$a^{\varphi(m)}\equiv 1\pmod m$$m$$g\in[1,m],(g,m)=1$$\{g,g^2,\ldots,g^{\varphi(m)}\}$$m$$m$$[1,m-1]$$\forall p<\varphi(m), g^{\varphi(m)}\neq 1$$\varphi(m)$$g^d\equiv 1\pmod m$$d$$\forall i,j\in[1,\varphi(m)],i\neq j,g^{i}\neq g^j\pmod m$$n$$n$$2,4,p^{a},2p^{a}$$p$$a$$g$$d_i$$\varphi(m)$$\forall i,g^{d_i}\neq 1$$g$$m$$p_i$$\varphi(m)$$\forall i,g^{\… text/html 2020-06-07T12:46:38+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:i_dont_know_png:potassium:sieve&rev=1591505198&do=diff 筛法 埃氏筛 列出所有数字，从小到大枚举，将枚举数的所有倍数筛掉。复杂度$O(n\log\log n)$，证明见这里。 void sieve(int n){ int i,j; isnp[0]=isnp[1]=1; for(i=2;i<=n;i++){ if(isnp[i])continue; pri[cnt++]=i; for(j=i;j<=n;j+=i)isnp[j]=1; } } $i$$i$$t=pri_j\times i$$i$$pri[j]$$t$$pri_j\mid i$$i$$pri[j]$$\forall k>j, i\times pri[k]$$i$$\frac{i}{pri[j]}\times pri[k]$$pri[j]$$O(n)$$\varphi(n)$$n$$\gcd(i,n)=1$$i$$n,m$$(m,n)=1$$\varphi(n\times m)=\varphi(n)\times \varphi(m)$$n=1$$\varphi(1)=1$$n=p$$\varphi(n)=p-1$$n=p^k$$\varphi(n)=p… text/html 2020-08-14T16:38:29+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:i_dont_know_png:potassium:sosdp&rev=1597394309&do=diff 等回去复制过来...