CVBB ACM Team 2020-2021:teams:legal_string:lgwza

2020-2021:teams:legal_string:lgwza:一般图最大匹配

Anonymous (anonymous@undisclosed.example.com) — 2020-08-19T23:57:49+0800

一般图最大匹配带花树算法 (Blossom Algorithm) 开花算法 (Blossom Algorithm，也被称为带花树)可以解决一般图最大匹配问题 (maximum cardinality matchings)。此算法由 Jack Edmonds 在 1961 年提出。经过一些修改后也可以解决一般图最大权匹配问题。此算法是第一个给出证明说最大匹配有多项式复杂度。$M$$v$$u$$u$$u$$u$$u$$G$$G'$$G$$G'$$G'$$G$$(u,v)$$h=LCA(u,v)$$h$$h$$h$$O(|E|^2)$$O(|V||E|^2)$

2020-2021:teams:legal_string:lgwza:主席树

Anonymous (anonymous@undisclosed.example.com) — 2020-08-29T14:30:52+0800

主席树例题洛谷 P3834 【模板】可持久化线段树 2（主席树）参考代码： #include using namespace std; const int N=2e5+5; int cnt; int a[N],b[N],rt[N]; int tr[N<<5],ls[N<<5],rs[N<<5]; void build(int& o,int l,int r){ o=++cnt; tr[o]=0; int mid=l+r>>1; if(l==r){ return; } build(ls[o],l,mid); build(rs[o],mid+1,r); } void xg(int& o,int l,int r,int pre,int x){ o=++cnt; ls[o]=ls[pre]; rs[o]=rs[pre]; tr[o]=tr[pre]+1; int mid=l+r>>1; if(l==r) return; if…

2020-2021:teams:legal_string:lgwza:二次剩余模板

Anonymous (anonymous@undisclosed.example.com) — 2020-09-02T23:14:08+0800

二次剩余模板给定 $n$ 和 $p$ 求解关于 $x$ 的方程 $x^2\equiv n\pmod{p}$ 例题 P5491 【模板】二次剩余 #include using namespace std; typedef long long ll; int t; ll n,p; ll w; struct num{ ll x,y; }; num mul(num a,num b,ll p){ num ans={0,0}; ans.x=((a.x*b.x%p+a.y*b.y%p*w%p)%p+p)%p; ans.y=((a.x*b.y%p+a.y*b.x%p)%p+p)%p; return ans; } ll binpow_real(ll a,ll b,ll p){//实部快速幂 ll ans=1; while(b){ if(b&1) ans=ans*a%p; a=a*a%p; b>>=1; } return ans; } ll b…

2020-2021:teams:legal_string:lgwza:二次剩余

Anonymous (anonymous@undisclosed.example.com) — 2021-01-17T20:48:35+0800

二次剩余一个数 $a$，如果不是 $p$ 的倍数且模 $p$ 同余于某个数的平方，则称 $a$ 为模 $p$ 的二次剩余。而一个不是 $p$ 的倍数的数 $b$，不同余于任何数的平方，则称 $b$ 为模 $p$ 的二次非剩余。对二次剩余求解，也就是对常数 $a$$$ x^2\equiv a\pmod p $$$x^2\equiv n\pmod p$$n$$p$$n$$\frac{p-1}{2}$$0$$\frac{p-1}{2}$$n$$p$$n$$p$$x$$x^2\equiv n\pmod p$$\pm x_0$$x_0^2\equiv n\pmod p$$$ \left(\frac n p\right)=\begin{cases}1,\,&p\nmid n\text{且}n\text{是}p\text{的二次剩余}\\ -1,\,&p\nmid n \text{且}n\text{不是}p\text{的二次剩余}\\ 0,\,&p\mid n\end{cases} $$$$ \left(\frac n p\right)\equiv n^{\frac{p-1}{2}}\p…

2020-2021:teams:legal_string:lgwza:匈牙利算法

Anonymous (anonymous@undisclosed.example.com) — 2020-08-07T21:49:47+0800

匈牙利算法二分图二分图（Bipartite graph）是一类特殊的图，它可以被划分为两个部分，每个部分内的点互不相连。下图是典型的二分图。 [ img] 可以看到，在上面的二分图中，每条边的端点都分别处于点集X和Y中。匈牙利算法主要用来解决两个问题：求二分图的$O(n^3)$$O(mn)$$O(n^2)$$O(n+m)$

2020-2021:teams:legal_string:lgwza:博弈论

Anonymous (anonymous@undisclosed.example.com) — 2021-07-18T22:26:09+0800

博弈论必胜点和必败点 * $P$ 点：必败点，换而言之，就是谁处于此位置，则在双方操作正确的情况下必败。 * $N$ 点：必胜点，处于此情况下，双方操作均正确的情况下必胜。必胜点和必败点的性质：$P$$N$$P$$P$$N$$(a_1,a_2,\cdots,a_n)$$P$$$ a_1\oplus a_2\oplus\cdots\oplus a_n=0 $$$(0,0,\cdots,0)$$0$$P$$(a_1,a_2,\cdots,a_n)$$a_1\oplus a_2\oplus\cdots\oplus a_n=0$$(b_1,b_2,\cdots,b_n)$$$ b_1\oplus b_2\oplus\cdots\oplus b_n\ne 0 $$$N$$(a_1,a_2\cdots,a_n)$$a_1\oplus a_2\oplus\cdots\oplus a_n\ne 0$$P$$a_1\oplus a_2\oplus\cdots\oplus a_n=k$$k$$1$$p$$a_1,a_2,\cdots,a_n$$a_i$$a_i$$p$$1$$i$$a_i…

2020-2021:teams:legal_string:lgwza:可持久化数组

Anonymous (anonymous@undisclosed.example.com) — 2020-08-29T01:50:15+0800

可持久化数组例题洛谷 P3919 【模板】可持久化线段树 1（可持久化数组）参考代码： #include using namespace std; const int N=1e6+5; int a[N]; int rt[N*20],ls[N*20],rs[N*20],tr[N*20],cnt; void build(int& o,int l,int r){ o=++cnt; if(l==r){ tr[o]=a[l]; return; } int mid=l+r>>1; build(ls[o],l,mid); build(rs[o],mid+1,r); } void xg(int& o,int l,int r,int pre,int pos,int v){ o=++cnt; ls[o]=ls[pre]; rs[o]=rs[pre]; tr[o]=tr[pre]; if(l==r){ tr[o]=v; …

2020-2021:teams:legal_string:lgwza:可逆背包

Anonymous (anonymous@undisclosed.example.com) — 2021-07-16T22:58:27+0800

可逆背包问题简介考虑这样一个问题：有 $n$ 个物品，体积分别是 $w_1,w_2,\cdots,w_n$，背包容量为 $m$，共有 $n$ 次询问，第 $i$ 次询问要求不选物品 $i$ 时共有多少选法装满背包。思路分析如果对于每个询问依次求 01 背包问题，单次询问需要 $O(nm)$$O(n^2m)$$O(m)$$i$$O(nm)$$n$$O(m)$$O(nm)$$n$$w_1,w_2,\cdots,w_n$$i$$n-1$$x$$cnt(i,x)$$i\in[1,n],x\in[1,m]$$cnt(i,x)$$n\times m$$cnt(i,x)$$1\le n,m\le 2000$$f[j][0]$$j$$f[j][1]$$j$$f[0][0]=f[0][1]=1$$s$$s$$[1,n/2] or [n/2+1,n]$$q$$(i,j)$$s[i],s[j]$$s$$52^2$$O(1)$$k$$c_1,c_2,\cdots,c_k$$i_1,i_2,\cdots,i_p$$c_{i_1}+c_{i_2}+\cdots+c_{i_p}=\dfrac{n}{…

2020-2021:teams:legal_string:lgwza:回文树

Anonymous (anonymous@undisclosed.example.com) — 2020-10-03T23:54:15+0800

回文树结构回文树大概长这样： [ img] 功能假设我们有一个串 $S$，$S$ 下标从 $0$ 开始，则回文树能做到如下几点： * 求串 $S$ 前缀 $0\sim i$ 内本质不同回文串的个数（两个串长度不同或者长度相同且至少有一个字符不同便是本质不同）。$S$$S$$1$$2$$i$$s$$s$$last$$num[]$$s$$s$$s$$s$$len[]$$cnt[]$$K$$cnt[]$$len[]$$w$$w^R$$x$$ww^Rww^R$$trans$

2020-2021:teams:legal_string:lgwza:图匹配

Anonymous (anonymous@undisclosed.example.com) — 2020-08-09T10:15:29+0800

图匹配匹配或是独立边集是一张图中没有公共点的集合。在二分图中求匹配等价于网络流问题。图匹配算法是信息学竞赛中常用的算法，总体分为最大匹配以及最大权匹配，先从二分图开始介绍，再进一步提出一般图的做法。$G=(V,E)$$V$$E$$(M(M\in E))$$\mid M\mid$$M$$M$$G$$G$$M$$M$$G$$M$$G=$$\mid V_1\mid\le\mid V_2\mid$$M$$G$$\mid M\mid=2\mid V_1\mid$$M$$V_1$$V_2$$G=,|V_1|\le|V_2|$$G$$V_1$$V_2$$S\subset V_1$$|S|\le|N(S)|$$N(S)=\Cup_{v_i\in S}{N(V_i)}$$S$$O(\sqrt VE)$$O(V^2E)$$O(V^2\log V+VE)$$O(V^2E)$$O(V^2E)$…

2020-2021:teams:legal_string:lgwza:割点和桥

Anonymous (anonymous@undisclosed.example.com) — 2020-10-28T16:08:17+0800

割点和桥割点 " 对于一个无向图，如果把一个点删除后这个图的极大连通分量数增加了，那么这个点就是这个图的割点（又称割顶）。" 如何实现？如果我们尝试删除每个点，并且判断这个图的连通性，那么复杂度会特别高。所以要介绍一个常用的算法：Tarjan。$u$$v$$u$$low_v\ge num_u$$u$$G=\{V,E\}$$e$$e\in E$$G-e$$e$$G$$low_v>num_u$$v$$u$$u$$low_v=num_u$$v$$u-v$

2020-2021:teams:legal_string:lgwza:增广路定理

Anonymous (anonymous@undisclosed.example.com) — 2020-08-09T20:45:41+0800

增广路定理 Berge’s lemma 这是最大匹配的一个重要理论。 * 交错路 (alternating path) 始于非匹配点且由匹配边与非匹配边交错而成。 * 增广路 (augmenting path) 是始于非匹配点且终于非匹配点的交错路。$a-b$$x$$P_x$$P_x$$a-b$$P_x$$a-b$$a-b$$x$$a-b$$x$

2020-2021:teams:legal_string:lgwza:序列自动机

Anonymous (anonymous@undisclosed.example.com) — 2020-10-06T14:28:39+0800

序列自动机定义序列自动机是接受且仅接受一个字符串的子序列的自动机。本文中用 $s$ 代指这个字符串。状态若 $s$ 包含 $n$ 个字符，那么序列自动机包含 $n+1$ 个状态。令 $t$ 是 $s$ 的一个子序列，那么 $\delta(start,t)$$t$$s$$i$$s[1..i]$$s[1..i-1]$$\delta(u,c)=\min\{i|i>u,s[i]=c\}$$c$$i>j$$s[i..|s|]$$s[j..|s|]$$$ \begin{array}{ll} 1 & \textbf{Input. } \text{A string } S\\ 2 & \textbf{Output. } \text{The state transition of the sequence automaton of }S \\ 3 & \textbf{Method. } \\ 4 & \textbf{for }c\in\Sigma\\ 5 & \qquad next[c]\gets null\\ 6 & \textbf{for }i\gets|S|\textbf{…

2020-2021:teams:legal_string:lgwza:强连通分量_tarjan_算法模板

Anonymous (anonymous@undisclosed.example.com) — 2020-08-24T11:32:07+0800

强连通分量——Tarjan 算法模板参考代码 #include using namespace std; const int N=1e4+5,M=2e5+5; int head[N],to[M],nxt[M],tot; int dfn[N],s[N],low[N],cnt,top; int sc;// SCC 个数 int scc[N];// 结点 i 所在 SCC 的编号 int sz[N];// 强连通 i 的大小 bool in[N]; void add(int u,int v){ nxt[++tot]=head[u]; head[u]=tot; to[tot]=v; } void tarjan(int u){ low[u]=dfn[u]=++cnt; s[++top]=u; in[u]=1; for(int i=head[u];i;i=nxt[i]){ int v=to[i]; if(!dfn[v]){ tarjan(v); …

2020-2021:teams:legal_string:lgwza:快速傅里叶变换_fft

Anonymous (anonymous@undisclosed.example.com) — 2021-02-15T22:05:25+0800

快速傅里叶变换(FFT) 原理 OI Wiki-快速傅里叶变换例题例 1 题意 P3803 【模板】多项式乘法（FFT）给定一个 $n$ 次多项式 $F(x)$，和一个 $m$ 次多项式 $G(x)$。求出 $F(x)$ 和 $G(x)$ 的卷积。题解通过 DFT 和 IDFT 两个过程，实现多项式由系数表示法 -> 点值表示法 -> 系数表示法。利用单位根的性质实现奇偶分治过程，时间复杂度 $O(n\log n)$$a,b$$a\times b$$1\le a,b\le 10^{1000000}$$n$$k$$k=\overline{a_{n-1}a_{n-2}\cdots a_2a_1a_0}=a_0+a_1x+a_2x^2+\cdots+a_{n-1}x^{n-1}(x=10)$$O(n\log n)$$n$$n$$q_1,q_2,\cdots,q_n$$$ F_j=\sum_{i=1}^{j-1}\frac{q_i\times q_j}{(i-j)^2}-\sum_{i=j+1}^{n}\frac{q_i\times q_j}{(i-j)^2}\\ …

2020-2021:teams:legal_string:lgwza:快速数论变换_ntt

Anonymous (anonymous@undisclosed.example.com) — 2021-02-15T22:04:43+0800

快速数论变换(NTT) 原理 OI Wiki-快速数论变换(NTT) 例题例 1 题意 P3803 【模板】多项式乘法（FFT）给定一个 $n$ 次多项式 $F(x)$，和一个 $m$ 次多项式 $G(x)$。求出 $F(x)$ 和 $G(x)$ 的卷积。$1\le n,m\le 10^6$ 题解找到模数 $p$，使得 $p=qn+1,(n=2^k)$，对于模 $p$ 的原根 $g$，$\displaystyle g_n\equiv g^q\equiv g^{\frac{p-1}{n}}$，可以看作 FFT 中 $n$ 次单位根 $\omega_n$ 的等价，因为它们都是各自所在群的生成元。所以 NTT 的代码只需把 FFT 中的 $\omega_n$$g^{\frac{p-1}{n}}$$a,b$$a\times b$$1\le a,b\le 10^{1000000}$$2$$F(x),G(x)$$F(x)*G(x)$$p$$p$$p=a\cdot 2^k+1$$1\le n,m\le 10^5,0\le a_i,b_i\le 10^9,2\le p\le 1…

2020-2021:teams:legal_string:lgwza:拆点

Anonymous (anonymous@undisclosed.example.com) — 2020-08-29T23:07:33+0800

拆点拆点是一种图论建模思想，常用于网络流，用来处理点权或者点的流量限制的问题，也常用于分层图。结点有流量限制的最大流如果把结点转化成边，那么这个问题就可以套板子解决了。$u,v$$$$u$$v$$$$k$$\text{dis}_{i,j}$$i$$j$$\text{dis}$$$ \text{dis}_{i,j}=\min\{\min\{\text{dis}_{from,j-1}\},\min\{\text{dis}_{from,j}+w\}\} $$$from$$i$$w$$j-1\ge k$$\text{dis}_{from,j}=\infty$$k+1$$u_i$$i$$u$$n$$m$$k$$s$$t$

2020-2021:teams:legal_string:lgwza:拉格朗日插值

Anonymous (anonymous@undisclosed.example.com) — 2020-09-17T14:08:02+0800

拉格朗日插值例题 " 例题 Luogu P4781【模板】拉格朗日插值" 给出 $n$ 个点 $P_i(x_i,y_i)$，将过这 $n$ 个点的最多 $n-1$ 次的多项式记为 $f(x)$，求 $f(k)$ 的值。拉格朗日插值法如图所示，将每一个点 $(x_i,y_i)$ 在 $x$ 轴上的投影 $(x_i,0)$ 记为 $H_i$。对每一个 $i$，我们选择一个点集 $\{P_i\}\cup\{H_j\mid1\le i\le n,j\ne i\}$$n$$n-1$$g_i(x)$$f(x)$$g_i(x)$$n$$g_i(x)(1\le i\le n)$$x_i$$y_i$$x_j(j\ne i)$$0$$g_i(x)$$$ g_i(x)=y_i\prod_{j\neq i}\frac{x-x_j}{x_i-x_j} $$$x_i$$f(x)=\sum_{i=1}^ng_i(x)$$g_i(x)$$i$$g_i$$P_i$$g_j$$H_i$$x_i$$y_i$$P_i$$$ f(x)=\sum_{i=1}^ny_i\prod_{j\ne i}\frac{x-…

2020-2021:teams:legal_string:lgwza:最小割

Anonymous (anonymous@undisclosed.example.com) — 2020-08-15T17:54:01+0800

最小割概念割对于一个网络流图 $G=(V,E)$，其割的定义为一种点的划分方式：将所有的点划分为 $S$ 和 $T=V-S$ 两个集合，其中源点 $s\in S$，汇点 $t\in T$。割的容量我们定义割 $(S,T)$ 的容量 $c(S,T)$ 表示所有从 $S$ 到 $T$ 的边的容量之和，即 $c(S,T)=\sum_{u\in S,v\in T}c(u,v)$$c(s,t)$$c(S,T)$$(S,T)$$c(S,T)$$f(s,t)_{max}=c(s,t)_{min}$$f(s,t)$$(S,T)$$f(s,t)=S_{出边的总流量}-S_{入边的总流量}\le S_{出边的总流量}=c(s,t)$$f$$s$$t$$S$$S$$f(s,t)=S_{出边的总流量}-S_{入边的总流量}=S_{出边的总流量}=c(s,t)$$f$$s$$\text{DFS}$$0$$S$$1$$\text{Dinic}$$e_1,e_2,e_3,\cdots,e_n$$A,B$$e_i$$A$$B$$a_{e_i}$$b_{e_i}$$C_i\subseteq A$$…

2020-2021:teams:legal_string:lgwza:杜教筛

Anonymous (anonymous@undisclosed.example.com) — 2020-09-07T12:29:49+0800

杜教筛积性函数在数论题目中，常常需要根据一些积性函数的性质，求出一些式子的值。积性函数：对于函数 $f(n)$ 有 $f(1)=1$ 且对于所有互质的 $a$ 和 $b$，总有 $f(ab)=f(a)f(b)$，则称 $f(n)$ 为积性函数。常见的积性函数有：$\sigma_0(n)=d(n)=\sum_{d\mid n }1$$\sigma(n)=\sum_{d\mid n}d$$\varphi(n)=\sum_{i=1}^n[\gcd(x,i)=1]$$\mu(n)=\begin{cases}1&\ n=1\\(-1)^k&\ \prod_{i=1}^k q_i=1\\0 &\ \max\{q_i\}>1 \end{cases}$$f(n)$$g(n)$$h(n)=f(n^p)$$h(n)=f^p(n)$$h(n)=f(n)g(n)$$h(n)=\sum_{d\mid n}f(d)g(\frac n d)$$h(n)$$f$$S(n)=\sum_{i=1}^nf(i)$$S(n)$$S\left(\left\lfloor\frac n i\right\rflo…

2020-2021:teams:legal_string:lgwza:扩展中国剩余定理

Anonymous (anonymous@undisclosed.example.com) — 2021-01-21T11:53:21+0800

扩展中国剩余定理例题【模板】扩展中国剩余定理题意：求解以下同余方程组 $$ \left\{\begin{array}{ccc} x &\equiv&a_1\pmod{m_1}\\ x &\equiv&a_2\pmod{m_2}\\ &\vdots&\\ x &\equiv& a_n\pmod{m_n}\\ \end{array}\right. $$ 不保证 $m_i$ 互质，保证有解题解：对于只有 $2$ 个方程的情况：$x\equiv a_1\pmod{m_1};x\equiv a_2\pmod{m_2}$，等价于 $x=a_1+m_1t_1=a_2+m_2t_2$，即 $m_1t_1-m_2t_2=a_2-a_1$，用扩展欧几里得解出 $t_1$，（若无解则方程组无解），从而得到 $x$$x\equiv x_0\pmod{\text{lcm}(m_1,m_2)}$$n$$n-1$…

2020-2021:teams:legal_string:lgwza:扩展_bsgs

Anonymous (anonymous@undisclosed.example.com) — 2021-01-22T15:49:15+0800

扩展BSGS 原理求解： $$ a^x\equiv b\pmod p $$ 其中 $a,p$ 不一定互质。当 $a\perp p$ 时，在模 $p$ 意义下 $a$ 存在逆元，因此可以用 BSGS 算法求解。于是我们想办法让他们变得互质。具体地，设 $d_1=\gcd(a,p)$。如果 $d_1\nmid b$，则原方程无解。否则我们把方程同时除以 $d_1$$$ \frac{a}{d_1}\cdot a^{x-1}\equiv\frac{b}{d_1}\pmod{\frac{p}{d_1}} $$$a$$\frac{p}{d_1}$$d_2=\gcd(a,\frac{p}{d_1})$$d_2\nmid\frac{b}{d_1}$$d_2$$$ \frac{a^2}{d_1d_2}\cdot a^{x-2}\equiv\frac{b}{d_1d_2}\pmod{\frac{p}{d_1d_2}} $$$a\perp \frac{p}{d_1d_2\cdots d_k}$$D=\prod_{i=1}^k d_i$$$ \frac{a^k}{D}\cdot a^{x-k}\…

2020-2021:teams:legal_string:lgwza:扫描线问题

Anonymous (anonymous@undisclosed.example.com) — 2021-09-17T11:17:12+0800

扫描线问题例 1 题意 P5490 【模板】扫描线求 $n$ 个矩形的面积并题解此问题可抽象出一个问题模型：给一初始全 0 的序列 $\{a_i\}_{i=1}^n$，每次操作如下：给定区间 $[l,r]$，令 $a_i=a_i+1,\forall i\in [l,r]$ 或 $a_i=a_i-1,\forall i\in [l,r]$，修改后立即询问 $\#\{a_i|a_i>0,i\in[1,n]\}$，保证任一修改后 $a_i\ge 0,\forall i\in[1,n]$ #include using namespace std; typedef long long ll; const int MAXN=1e6+5; #define ls o<<1 #define rs o<<1|1 ll X[MAXN<<1]; // 横线 struct Line{ // 左右端点的横坐标,竖坐标 ll l,r,h; // 1 表示下底边，-1 表示上底边 int mark; // 按高度排序 …

2020-2021:teams:legal_string:lgwza:数位_dp

Anonymous (anonymous@undisclosed.example.com) — 2020-08-05T23:09:41+0800

数位 DP 经典题型数位 DP 问题往往都是这样的题型，给定一个闭区间 $[l,r]$，让你求这个区间中满足某种条件的数的总数。 " 例题 SCOI2009 windy 数题目大意：给定一个区间 $[l,r]$，求其中满足条件不含前导 0 且相邻两个数字相差至少为 2 $ans_i$$[1,i]$$ans_r-ans_{l-1}$$n$$n$$n$$f(i,st,op)$$i$$st$$op$$op=1$$op=0$$\text{gcd}$$$ f(i,st,op)=\sum^{maxx}_{k=1}f(i+1,k,op=1\ and\ k=maxx)\quad (\mid st-k\mid\ge 2) $$$k$$maxx$$op=1$$f$…

2020-2021:teams:legal_string:lgwza:普通莫队算法

Anonymous (anonymous@undisclosed.example.com) — 2020-08-03T23:34:50+0800

普通莫队算法形式假设 $n=m$，那么对于序列上的区间询问问题，如果从 $[l,r]$ 的答案能够 $O(1)$ 扩展到 $[l-1,r],[l+1,r],[l,r+1],[l,r-1]$ （即与 $[l,r]$ 相邻的区间）的答案，那么可以在 $O(n\sqrt{n})$ 的复杂度内求出所有询问的答案。实现离线后排序，顺序处理每个询问，暴力从上一个区间的答案转移到下一个区间答案（一步步移动即可）。$[l,r]$$l$$r$$n$$c_i$$m$$l$$r$$l$$r$$[l,r]$$l$$r$$O(n)$$[i,i]$$col[i]$$i$$ans$$k$$ans$$C^2_{col[k]+1}-C^2_{col[k]}$$ans$$C^2_{col[k]}-C^2_{col[k]-1}$$\displaystyle\frac{ans}{C^2_{r-l+1}}$$C^2_a=\displaystyle\frac{a(a-1)}{2}$$C^2_{a+1}-C^2_a=\displaystyle\frac{(a+1)a}{2}-\displaystyle\frac{a…

2020-2021:teams:legal_string:lgwza:状压_dp

Anonymous (anonymous@undisclosed.example.com) — 2020-08-04T23:05:55+0800

状压 DP 学习状压 DP 之前，请确认你已经完成了动态规划基础部分内容的学习。（同时建议学习位运算部分的内容）状压 DP 简介状压 DP 是动态规划的一种，通过将状态压缩为整数来达到优化转移的目的。$N\times N$$K$$8$$f(i,j,l)$$i$$j$$l$$j$$j$$sta(x)$$j$$x$$f(i,j,l)=\sum f(i-1,x,l-sta(x))$

2020-2021:teams:legal_string:lgwza:生成函数理论_基本定义

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

生成函数理论 1 基本定义定义 1 数列 $\{a_n\}_{n=0}^{\infty}$ 的普通生成函数是下面的形式级数： $$ f(x)=\sum_{n=0}^{\infty}a_nx^n. $$ 定义 2 数列 $\{a_n\}_{n=0}^{\infty}$ 的指数型生成函数是下面的形式级数： $$ f(x)=\sum_{n=0}^{\infty}\frac{a_n}{n!}x^n. $$ 定义 3 数列 $\{a_n\}_{n=1}^{\infty}$ 的 Dirichlet 生成函数是下面的形式级数： $$ f(s)=\sum_{n=1}^{\infty}\frac{a_n}{n^s}. $$$\{1\}_{n=0}^{\infty}$$$ \sum_{n=0}^{\infty}x^n=\frac{1}{1-x}. $$$\{1\}_{n=0}^{\infty}$$$ \sum_{n=0}^{\infty}\frac{x^n}{n!}=e^x. $$$\{1\}_{n=0}^{\infty}$$$ \sum_{n=1}^{\infty}\f…

2020-2021:teams:legal_string:lgwza:生成函数理论_1_基本定义

Anonymous (anonymous@undisclosed.example.com) — 2021-02-09T18:28:01+0800

2020-2021:teams:legal_string:lgwza:生成函数理论_2_基本例子

Anonymous (anonymous@undisclosed.example.com) — 2021-02-10T15:55:31+0800

生成函数理论2 基本例子例 1 设 $n\ge 1$，$X_n=\{1,2,\cdots,n\}$。记 $a_n$ 为 $X_n$ 的子集个数，求 $a_n$。解：易知 $a_n=2a_{n-1}(n\ge 1)$，$\{a_n\}_{n=0}^{\infty}$ 的普通生成函数为 $$ \begin{align} f(x)&=\sum_{n=0}^{\infty}a_nx^n=1+\sum_{n=1}^{\infty}a_nx^n=1+\sum_{n=0}^{\infty}2a_nx^{n+1}\\ &=1+2x\sum_{n=0}^{\infty}a_nx^n=1+2xf(x), \end{align} $$ 所以 $$ f(x)=\frac{1}{1-2x}=\sum_{n=0}^{\infty}(2x)^n=\sum_{n=0}^{\infty}2^nx^n. $$ 比较系数得 $a_n=2^n$. 例 2 设有三种物体 $a,b,c$$a_n$$n$$\{a_n\}_{n=0}^{\infty}$$$ \begin{align} ((ax)^0&+(a…

2020-2021:teams:legal_string:lgwza:生成函数理论_3_普通生成函数

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

生成函数理论 3——普通生成函数定义 1 若形式级数 $f(x)=\sum_{n=0}^{\infty}a_nx^n$ 与 $g(x)=\sum_{n=0}^{\infty}b_nx^n$ 满足 $f(x)g(x)=1$，则称 $g(x)$ 为 $f(x)$ 的乘法逆。性质 2 形式级数 $f(x)=\sum_{n=0}^{\infty}a_nx^n$ 有乘法逆的充分必要条件是 $a_0\ne 0$。性质 3 设形式级数 $f(x)=\sum_{n=0}^{\infty}a_nx^n$ 与 $g(x)=\sum_{n=0}^{\infty}b_nx^n$ 互为复合逆，并且 $a_0=0$，则有 $b_0=0$$a_1\ne 0,b_1\ne 0$$f(x)=\sum_{n=0}^{\infty}a_nx^n$$f'(x)=0$$f(x)$$a_0$$f(x)=\sum_{n=0}^{\infty}a_nx^n$$f'(x)=f(x)$$f(x)=Ce^x$$C$$f(x)=\sum_{n=0}^{\infty}a_nx^n$$\{a_{n+1}\}_{n=0}^{\i…

2020-2021:teams:legal_string:lgwza:生成函数理论_4_指数型生成函数

Anonymous (anonymous@undisclosed.example.com) — 2021-02-18T14:41:31+0800

生成函数理论 4——指数型生成函数事实 1 若 $\displaystyle f(x)=\sum_{n=0}^{\infty}\frac{a_n}{n!}x^n$，则 $\displaystyle \{a_{n+1}\}_{n=0}^{\infty}$ 的指数型生成函数是 $$ \sum_{n=0}^{\infty}\frac{a_{n+1}}{n!}x^n=\sum_{n=1}^{\infty}\frac{na_n}{n!}x^{n-1}=f'(x). $$ 性质 2 若 $\displaystyle f(x)=\sum_{n=0}^{\infty}\frac{a_n}{n!}x^n$，则 $\displaystyle \{a_{n+k}\}_{n=0}^{\infty}$ 的指数型生成函数是 $\displaystyle D^kf$。例 3 回忆 Fibonacci 数列 $\{f_n\}_{n=0}^{\infty}$，满足 $f_{n+2}=f_{n+1}+f_n$，初始条件为 $f_0=0,f_1=1$。用生成函数的方法再次求解 $f_n$$f(x)$$\{f…

2020-2021:teams:legal_string:lgwza:生成函数理论_5_一些例子

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

生成函数理论 5 基本应用例 1 P2000 拯救世界依照题意可列出 10 个条件的生成函数 $f_i(x)$，将它们相乘再化简即可。 * $f_1(x)=(1+x^6+x^{12}+\cdots)=\frac{1}{1-x^6}$ * $f_2(x)=(1+x+x^2+\cdots+x^9)=\frac{1-x^{10}}{1-x}$ * $f_3(x)=(1+x+x^2+\cdots+x^5)=\frac{1-x^6}{1-x}$ * $f_4(x)=(1+x^4+x^8+\cdots)=\frac{1}{1-x^4}$ * $f_5(x)=(1+x+x^2+\cdots+x^7)=\frac{1-x^8}{1-x}$ * $f_6(x)=(1+x^2+x^4+\cdots)=\frac{1}{1-x^2}$ * $f_7(x)=(1+x)=\frac{1-x^2}{1-x}$ * $f_8(x)=(1+x^8+x^{16}+\cdots)=\frac{1}{1-x^8}$ * $f_9(x)=(1+x^{10}+x^{20}+\c…

2020-2021:teams:legal_string:lgwza:类_dinic_算法

Anonymous (anonymous@undisclosed.example.com) — 2020-08-20T15:50:50+0800

类 Dinic 算法我们可以在 Dinic 算法的基础上进行改进，把 BFS 求分层图改为用 SPFA （由于有负权边，所以不能直接用 Dijkstra）来求一条单位费用之和最小的路径，也就是把 $w(u,v)$ 当做边权然后在残量网络上求最短路，当然在 DFS 中也要略作修改。这样就可以求得网络流图的 $(u,v,w,c)$$w$$c$$(u,v,w,c)$$(v,u,0,-c)$$-c$$O(nmf)$$f$

2020-2021:teams:legal_string:lgwza:网络流简介

Anonymous (anonymous@undisclosed.example.com) — 2020-08-12T00:05:19+0800

网络流简介网络首先，请分清楚网络（或者流网络，Flow Network）与网络流（Flow）的概念。网络是指一个有向图 $G=(V,E)$。每条边 $(u,v)\in E$ 都有一个权值 $c(u,v)$，称之为容量（Capacity），当 $(u,v)\notin E$ 时有 $c(u,v)=0$。其中有两个特殊的点：源点（Source）$s\in V$$t\in V,(s\ne t)$$f(u,v)$$(u\in V,v\in V)$$f(u,v)\le c(u,v)$$f(u,v)=-f(v,u)$$\forall x\in V-\{s,t\},\sum_{(u,v)\in E}f(u,x)=\sum_{(x,v)\in E}f(s,v)$$f$$G$$(u,v)\in E$$f(u,v)$$c(u,v)-f(u,v)$$\sum_{(s,v)\in E}f(s,v)$$$ f(u,v)=\left\{\begin{aligned} &f(u,v),&(u,v)\in E\\ &-f(v,u),&(v,u)\in E\\ &0,&(u,v)\notin…

2020-2021:teams:legal_string:lgwza:虚树

Anonymous (anonymous@undisclosed.example.com) — 2021-03-06T19:03:54+0800

虚树引子「SDOI2011」消耗战题目描述在一场战争中，战场由 $n$ 个岛屿和 $n-1$ 个桥梁组成，保证每两个岛屿间有且仅有一条路径可达。现在，我军已经侦查到敌军的总部在编号为 $1$ 的岛屿，而且他们已经没有足够多的能源维系战斗，我军胜利在望。已知在其他 $k$$1$$m$$n$$n-1$$u,v,w$$u$$v$$c$$1\le u,v\le n$$1\le c\le 10^5$$n+1$$m$$m$$k_i$$i$$k_i$$k_i$$h_1,h_2,\cdots,h_k$$m$$100\%$$2\le n\le 2.5\times10^5,\sum k_i\le 5\times10^5,1\le k_i\le n-1$$Dp(i)$$i$$w(a,b)$$a$$b$$i$$v$$v$$Dp(i)=Dp(i)+\min\{Dp(v),w(i,v)\}$$v$$Dp(i)=Dp(i)+w(i,v)$$O(nq)$$\lceil$$\rfloor$$1$$1$$n$$O(k^2)$$1$$1$$6,4,7$$[4,6,7]$$1$$4$$1$$1$$4$$LCA…

2020-2021:teams:legal_string:lgwza:2-sat

Anonymous (anonymous@undisclosed.example.com) — 2020-08-25T19:21:12+0800

2-SAT " SAT 是适定性（Satisfiability）问题的简称。一般形式为 k - 适定性问题，简称 k-SAT。而当 $k>2$ 时该问题为 NP 完全的。所以我们只研究 $k=2$ 的情况。" 定义 2-SAT，简单地说就是给出 $n$ 个集合，每个集合有两个元素，已知若干个 $$$a$$b$$a$$b$$n$$a$$A$$B$$(\neg a);b$$C$$\neg b$$(a \vee b)$$a,b$$\neg a\Rightarrow b\ \wedge \neg b\Rightarrow a $$a$$b$$b$$a$$a1,a2$$b1,b2$$a1$$b2$$(a1,b1)$$(b2,a2)$$a1$$b1$$b2$$a2$$\neg x$$x$$x$$x$$\neg x$$x$$O(n+m)$$n$$1$$2n$$2$$n$$a1$$a2$$a1$$a2$$a2$$a1$$k(k>3)$$n$…

2020-2021:teams:legal_string:lgwza:codeforces_1486

Anonymous (anonymous@undisclosed.example.com) — 2021-02-22T19:59:20+0800

Codeforces Round #703 (Div. 2) 比赛链接 C2. Guessing the Greatest (hard version) 标签交互题、二分、次大值、最大值题意交互题。给定一固定的数列，每次可询问一区间的次大值的位置，要求在 20 次询问内找到该数列的最大值的位置。$2\le n\le 10^5,1\le l0$$x$$O(n\log n)$$w$$a\rightarrow b\rightarrow c$$(w_{ab}+w_{bc})^2$$1$$-1$$w_i\leq 50$$v$…

2020-2021:teams:legal_string:lgwza:codeforces_1492

Anonymous (anonymous@undisclosed.example.com) — 2021-02-24T06:45:42+0800

Codeforces Round #704 (Div. 2) 比赛链接 C. Maximum width 标签子序列，贪心题意给定两个字符串 $s,t$，长度分别为 $n,m(m\leq n)$，保证 $t$ 是 $s$ 的一个子序列，求子序列 $t$ 在 $s$ 中两个字符的间隔的最大值是多少。题解用 $left_i$ 记录 $t$$s$$t_i=s_{left_i}$$left_i$$right_i$$t$$s$$t_i=s_{right_i}$$right_i$$\max_{i=1}^{m-1}\{right_{i+1}-left_i\}$$3$$a,b,k(0\leq a;1\leq b;0\leq k\leq a+b\leq 2\cdot10^5)$$x,y(x\geq y)$$x,y$$a$$0$$b$$1$$x-y$$k$$1$$x$$11\cdots 1100\cdots 00$$y$$x$$1$$x-y$$1$$+1$$k\leq a$$k>a$$1$$k$$+1$$k\in [0,a+b-2]$$a=0,b=1,k=0$…

2020-2021:teams:legal_string:lgwza:codeforces_round

Anonymous (anonymous@undisclosed.example.com) — 2020-08-10T01:21:57+0800

Codeforces Round #663 (Div. 2)

2020-2021:teams:legal_string:lgwza:codeforces_round_662_div._2

Anonymous (anonymous@undisclosed.example.com) — 2020-08-10T01:23:42+0800

Codeforces Round #662 (Div. 2)

2020-2021:teams:legal_string:lgwza:codeforces_round_663_div._2

Anonymous (anonymous@undisclosed.example.com) — 2020-08-10T01:24:05+0800

Codeforces Round #663 (Div. 2)

2020-2021:teams:legal_string:lgwza:codeforces_round_664_div._2

Anonymous (anonymous@undisclosed.example.com) — 2020-08-13T08:45:12+0800

比赛链接

2020-2021:teams:legal_string:lgwza:dinic_算法

Anonymous (anonymous@undisclosed.example.com) — 2020-08-16T15:26:46+0800

Dinic 算法 Dinic 算法可用于求解网络最大流问题。 Dinic 算法的过程是这样的：每次增广前，我们先用 BFS 来将图分层。设源点的层数为 $0$，那么一个点的层数便是它离源点的最近距离。通过分层，我们可以干两件事情：$1$$n$$m$$O(n^2m)$$O(m\sqrt n)$

2020-2021:teams:legal_string:lgwza:manacher_算法

Anonymous (anonymous@undisclosed.example.com) — 2020-10-02T14:12:09+0800

Manacher 算法描述给定一个长度为 $n$ 的字符串 $s$，请找到所有对 $(i,j)$ 使得子串 $s[i\ldots j]$ 为一个回文串。当 $t=t_{rev}$ 时，字符串 $t$ 是一个回文串（$t_{rev}$ 是 $t$ 的反转字符串）。更进一步的描述显然在最坏情况下可能有 $O(n^2)$$i=0\ldots n-1$$d_1[i]$$d_2[i]$$i$$s=\mathtt{abababc}$$s[3]=b$$d_1[3]=3$$$ a\ \overbrace{b\ a\ \underset{s_3}{b}\ a\ b}^{d_1[3]=3}\ c $$$s=\mathtt{cbaabd}$$s[3]=a$$d_2[3]=2$$$ c\ \overbrace{b\ a\ \underset{s_3}{a}\ b}^{d_2[3]=2}\ d $$$i$$l$$i$$l-2$$l-4$$d_1[i]$$d_2[i]$$d_1[]$$d_2[]$$O(n\log n)$$O(n)$$i$$1$$O(n^2)$$d_1[]$$d_2[]$$(l,r…

2020-2021:teams:legal_string:lgwza:spfa_dijkstra_最短路模板

Anonymous (anonymous@undisclosed.example.com) — 2020-08-21T08:53:10+0800

SPFA+Dijkstra 最短路模板参考代码 #include using namespace std; const int N=1e5+5,M=1e6+5,INF=2147483647; int head[N],to[M],nxt[M],dis[N],cost[M]; bool vis[N]; int tot=1; int n; void add(int u,int v,int c){ nxt[++tot]=head[u]; head[u]=tot; to[tot]=v; cost[tot]=c; } void dijkstra(int s){ for(int i=1;i<=n;i++) dis[i]=INF; dis[s]=0; priority_queue,vector>,greater>>pq; pq.push(make_pair(0,s)); while(!pq.empty()){ …

2020-2021:teams:legal_string:lgwza:splay

Anonymous (anonymous@undisclosed.example.com) — 2020-08-22T22:11:34+0800

Splay " 如何用 $\text{Splay}$ 维护二叉查找树" 简介 $\text{Splay}$ 是一种二叉查找树，它通过不断将某个结点旋转到根结点，使得整棵树仍然满足二叉查找树的性质，并且保持平衡而不至于退化为链，它由 Daniel Sleator 和 Robert Tarjan 发明。$<$$<$$rt$$tot$$fa[i]$$ch[i][0/1]$$val[i]$$cnt[i]$$sz[i]$$\text{maintain(x)}$$x$$\text{size}$$\text{get(x)}$$x$$\text{clear(x)}$$x$$\text{Splay}$$\text{Splay}$$\text{root}$$\text{Splay}$$x$$y$$y$$x$$x$$y$$x$$y$$y$$x$$y$$z$$z$$y$$x$$x$$z$$\text{Splay}$$6$$x$$x$$x$$1,2$$x$$x$$x$$3,4$$x$$x$$x$$5,6$$6$$\text{Splay}$$k$$k$$\text{Splay}$$\text{Splay}…

2020-2021:teams:legal_string:lgwza:stirling_数_理论

Anonymous (anonymous@undisclosed.example.com) — 2021-03-05T18:30:55+0800

Stirling 数——理论定义 1 对于正整数 $n$，$k$，定义 $c(n,k)$ 为 $n$ 元对称群 $S_n$ 中恰含 $k$ 个轮换（即恰可写成 $k$ 个不交轮换的乘积）的置换个数（注意，不动点也看做一个轮换）。称 $s(n,k)=(-1)^{n-k}c(n,k)$ 为第一类 Stirling 数，也常常称 $c(n,k)$$c(0,0)=1$$n\ge 1$$c(n,0)=c(0,n)=0$$n\geq 1$$k\ge 1$$c(n,k)$$$ c(n,k)=(n-1)c(n-1,k)+c(n-1,k-1). $$$\Box$$\sigma$$S_n$$k$$\sigma(n)=n$$n$$\sigma$$\sigma$$S_{n-1}$$k-1$$c(n-1,k-1)$$\sigma(n)\neq n$$\sigma$$n$$S_{n-1}$$k$$\sigma$$S_{n-1}$$k$$n-1$$(n-1)c(n-1,k)$$$ c(n,k)=(n-1)c(n-1,k)+c(n-1,k). $$$\Box$$\{c(n,k)\}_{n=1}^{\infty…