焚诀

A1ex_5yn7ax · 2025-11-30 18:24:50 · 个人记录

数论部分

组合计数

小球模型

以下假定 n 个小球，m 个盒子

小球之间没有区别，盒子之间没区别，盒子不能为空：

$dp_{i,j}=dp_{i-1,j-1}+dp_{i-j,j}

有点难理解但

-
--
----
-----

每次都是加一条横线

小球之间没有区别，盒子之间没区别，盒子能为空：

把上面的 dp_{n,i} 累加起来即可

小球之间没有区别，盒子之间有区别，盒子不能为空：

插板法，在 n-1 个空隙里放 m-1 个板子答案为 C_{n-1}^{m-1}

小球之间没有区别，盒子之间有区别，盒子为空：

先加 m 个小球，继续插板，有 C_{n+m-1}^{n-1} 种插法，最后拿掉加的 m 个就和原题等价了

小球之间有区别，盒子之间没有区别，盒子不能为空：

$dp_{i,j}=dp_{i-1,j-1}+dp_{i,j-1}*i

小球之间有区别，盒子之间没有区别，盒子能为空：

把上面的 dp_{i,n} 累加起来即可

小球之间有区别，盒子之间有区别，盒子不能为空：

$dp_{i,j}=dp_{i-1,j-1} \times (m-i+1)+dp_{i,j-1}*i

小球之间有区别，盒子之间有区别，盒子能为空：

每个小球都有 m 个选择，直接就是 m^n

二项式反演

即广义容斥原理

** 反演：简而言之为两种函数之间的变换关系 **

二项式反演：

形式 1：

$g_{n}=\sum_{i=0}^{n}f_{i}

f_{n}=\sum_{i=0}^{n}(-1)^{n-i}C_{n}^{i}g_{i}

形式 2：

$g_{k}=\sum_{i=k}^{n} C_{i}^{k}f_{i}

f_{k}=\sum_{i=k}^{n} (-1)^{i-k} C_{i}^{k}g_{i}

数论函数

常见数论（积性）函数：

** 单位函数 **\varepsilon (n)=[n=1]
常数函数 \mathbb{1}(n)=1
恒等函数 \text{id}_k(n)=n^k
除数函数 \sigma_k(n)=\sum_{d\mid n}d^k\ 特殊的，\sigma_0(n) 习惯称为 d(n)，\sigma_1(n) 常省略下标写作 \sigma(n)。

数论分块

将一个区间分成 \sqrt n 块，每块的 \lfloor\frac ni\rfloor 相同，做到 \mathcal O(\sqrt n) 求出 \lfloor\frac ni\rfloor 的前缀和。例如

\begin{aligned}\sum^{n}_{i = 1}d(i) &= \sum ^{n}_{i = 1}\sum_{jk}[jk=i] &(最基础的变形)\\&= \sum_{ij}[ij\le n] \\&= \sum^n_{i = 1}\lfloor \frac{n}{i} \rfloor &\\\end{aligned}

exgcd

裴蜀定理：若对于 ax+by=c 有 \gcd(a,b)\nmid c 则此方程无解

若有解，则先解 ax+by= \gcd (a,b) 再乘 \frac{c}{\gcd(a,b)}

从 \gcd 着手

若 ax+by= \gcd (a,b)

递归求解 bx'+(a\text{ mod }b)y'=\gcd(b,a\text{ mod }b)

x=\begin{cases} 1\ \ (b=0)\\y'\ (others)\end{cases}

y=\begin{cases}0\ (b=0)\\x'-\lfloor\frac ab\rfloor\times y'\ (others)\end{cases}

void exgcd(int a,int b,int &x,int &y){
    if(b==0){
        x=1,y=0;
        return;
    }
    int x0,y0;
    exgcd(b,a%b,x0,y0);
    x=y0;
    y=x0-(a/b)*y0;
}

逆元：

若有：

a\times b\equiv1\pmod p

则称 b 是 a 在模 p 下的逆元，记作 a^{-1}，若 a, p 不互质则不存在这样的 a^{-1}。

原式可化为 ab-kp=1，ex \gcd 即可
若 p 是质数，则有 a^{-1}=a^{p-2}
线性递推 1\sim n! 的逆元有以下式子：
\frac 1{(n-1)!}\equiv\frac 1{n!}\times n\pmod p QED.
我们 \mathcal O(\log n) 计算出 n! 的逆元，即可倒推。

CRT

求方程组：

\left\{\begin{matrix} x\equiv a_1\pmod{b_1}\\ x\equiv a_2\pmod{b_2}\\ x\equiv a_3\pmod{b_3}\\ ...\\ x\equiv a_n\pmod{b_n}\\ \end{matrix}\right.

的一个可行解（保证 b_i 互质）。

我们可以发现，我们实际只需考虑这几组方程：

x_1\equiv a_1\pmod{b_1}\\ x_1\equiv 0\pmod{b_2}\\ x_1\equiv 0\pmod{b_3}\\ ...\\ x_1\equiv 0\pmod{b_n}\\ \end{matrix}\right.$ $\left\{\begin{matrix} x_2\equiv 0\pmod{b_1}\\ x_2\equiv a_2\pmod{b_2}\\ x_2\equiv 0\pmod{b_3}\\ ...\\ x_2\equiv 0\pmod{b_n}\\ \end{matrix}\right.$ $\left\{\begin{matrix} x_3\equiv 0\pmod{b_1}\\ x_3\equiv 0\pmod{b_2}\\ x_3\equiv a_3\pmod{b_3}\\ ...\\ x_3\equiv 0\pmod{b_n}\\ \end{matrix}\right.$ $\text{...}$ $\left\{\begin{matrix} x_n\equiv 0\pmod{b_1}\\ x_n\equiv 0\pmod{b_2}\\ x_n\equiv 0\pmod{b_3}\\ ...\\ x_n\equiv a_n\pmod{b_n}\\ \end{matrix}\right.

最后我们把所有解合并，\sum x_i 即为答案（可以思考一下）。

于是我们观察其中一个方程组研究，为了方便，我们取第一个处理，其他同理。

我们发现方程可以进一步化为 \left\{\begin{matrix} y_1\equiv 1\pmod{b_1}\\ y_1\equiv 0\pmod{b_2}\\ y_1\equiv 0\pmod{b_3}\\ ...\\ y_1\equiv 0\pmod{b_n}\\ \end{matrix}\right.，其中 y_i\times a_i=x_i。

由于需要保证解能被其他模数整除，我们设 M=\prod b_i,M_i=\frac M{b_i}，则我们需要构造 t_1 使得 M_1\times t_1\equiv1\pmod {b_1}。

其实 t_1 就是 M_1 模 p_1 意义下的逆元，于是 x_1=a_1y_1=a_1M_1t_1。

于是 x=\sum x_i=\sum a_iM_it_i。

EXCRT

我们可以将方程化为

\begin{aligned} \left\{\begin{matrix} x_0= a_1-k_1b_1\\ x_0= a_2-k_2b_2\\ \end{matrix}\right. &\Leftrightarrow a_1-k_1b_1=a_2-k_2b_2\\ &\Leftrightarrow k_2b_2-k_1b_1=a_2-a_1 \end{aligned}

注意到这是一个不定方程，我们可以用 \texttt{ex \gcd } 求解，得到一组特解 k_1,k_2。

则它们的通解即为

\begin{aligned} \left\{\begin{matrix} K_1=k_1+t\times\frac{b_2}{\gcd(b_1,b_2)}\\ K_2=k_2+t\times\frac{b_1}{\gcd(b_1,b_2)} \end{matrix}\right. \end{aligned}

我们代入之前的任意一个方程，得到

\begin{aligned} x_0&=a_1-K_1b_1\\ &=a_1-k_1b_1-t\times\frac{b_1b_2}{\gcd(b_1,b_2)}\\ &=a_1-k_1b_1-t\times\operatorname{lcm}(b_1,b_2)\\ \end{aligned}

于是得到

x_0\equiv a_1-k_1b_1\pmod{\operatorname{lcm}(b_1,b_2)}

其中 a_1,b_1 均已知，k_1 已求出，于是我们便成功合并了两个方程。

欧拉函数

定义为 1\sim n 中与 n 互质的数的个数。形式化的说，\varphi(n)=\sum^n_{i=1}[\gcd(n,i)=1]

结论 1：\varphi(n)=n-1，其中 n 是一个质数。

证明：显然只有 n 本身与 n 不互质。
结论 2：欧拉函数为积性函数，即 \varphi(nm)=\varphi(n)\varphi(m)( 当 n\perp m)。
结论 3：\varphi(p^k)=p^k-p^{k-1}，其中 p 是一个质数。

证明：将 p^k 化为 p\times p^{k-1} 可以发现，只有 p 的前 p^{k-1} 个倍数与 p^k 不互质。
结论 4：利用结论 2 和结论 3，我们可以得到欧拉函数的另一种形式：

\varphi(n)=n\times \prod\frac{p_i-1}{p_i}

其中 p\in \text{prime},\prod p_i^{k_i}=n。

证明：将 n 化为唯一分解形式，则有

\begin{aligned} \varphi(n)&=\prod\varphi(p_i^{k_i})\\ &=\prod p_i^{k_i}(1-\frac{1}{p_i})\\ &=\prod p_i^{k_i}\times\prod(1-\frac{1}{p_i})\\ &=n\times\prod\frac{p_i-1}{p_i} \end{aligned}

结论 5：\varphi(nm)\varphi(\gcd(n,m))=\varphi(n)\varphi(m)\gcd(n,m)。

证明：由上化简可得。
结论 6：n=\sum_{d\mid n}\varphi(d)。

证明 1：我们构造一个函数 f(x)=\sum_{1\le d\le n}[\gcd(n,d)=x]，则 n=\sum^n_{i=1}f(i)。易知 f(x)=\varphi(\frac nx)，则结论 5 成立。

证明 2：我们有分数 \frac 1n,\frac 2n,\frac 3n,...,\frac nn，将其中能约分的约分，则对于任意数 d(d\le n)，分母为 d 的分数个数为 \varphi(d)，则结论 5 成立。

进一步，我们还可以得到 \gcd(a,b)=\sum_{d\mid a,d\mid b}\varphi(d)=\sum_d[d\mid a][d\mid b]\varphi(d)（这个结论有些地方称之为欧拉反演）。
结论 7：
\varphi(n!)= \begin{aligned} \left\{\begin{matrix} \varphi((n-1)!)\times n,&n\notin\text{prime}\\ \varphi((n-1)!)\times (n-1),&n\in\text{prime}\\ \end{matrix}\right. \end{aligned}
由结论 4 可得。

筛 n=n'*p 时

若 p\perp n'，可以使用结论 2

若 p\mid n', 说明 n' 包含 n 的所有质因子，所以 \varphi(n)=p\times n'\times\prod(1-\frac{p_i-1}{p_i})=p\times\varphi(n')。
```
bool vis[N];
int phi[N];
int p[N],tot;
void init(int n){
  for(int i=2;i<=n;i++){
      if(!vis[i]) p[++tot]=i,phi[i]=i-1;
      for(int j=1;j<=tot && i*p[j]<=n;j++){
          vis[i*p[j]]=true;
          if(i%p[j]==0) {
              phi[i*p[j]]=phi[i]*p[j];
              break;
          }else phi[i*p[j]]=phi[i]*(p[j]-1);
      }
  }
}
```
类似地，奇性函数都可筛出来
\mu
```
void getmu(int n) {
  for(int i=1;i <= n;i++)  mu[i]=1, vis[i];
  for(int i=2;i <= n;i++) {
      if(vis[i])  continue;
      mu[i] = -1;
      for(int j = 2*i; j <= n;j += i) {
          vis[j] = 1;
          if(j % (i*i) == 0)  mu[j] = 0;
          else  mu[j] *= -1;
      }
  }
}
```
狄利克雷卷积：

狄利克雷卷积是是数论函数之间的二元运算，符号为 \ast。

具体来说，定义两个数论函数 f(x) 和 g(x)，定义卷积结果为 h(x)。

则：
h(x)=\sum_{d\mid n}f(d)g(\frac xd)
记为 h=f\ast g。

狄利克雷卷积遵循交换律、结合律、分配律。
- 定义 1：若有两数论函数 f,g 满足 f\ast g=\varepsilon，其中 \varepsilon 为单位函数，则 g 为 f 的逆元，记作 f^{-1}。
- 结论 1：如果 f,g 为积性函数，则 f\ast g 也为积性函数。由上易证。
- 结论 2：如果 f 为积性函数，则 f^{-1} 也为积性函数。由上易证。
一些常见的卷积：
- \text{id}_k\ast \mathbb1=\sigma_k
- \varphi\ast\mathbb1=\text{id}
- \mathbb1\ast\mathbb1=d
- 莫比乌斯反演：
莫比乌斯函数有两种定义：
- 常数函数 \mathbb1 的逆元称为 \mu。
- 直接定义 \mu(n)= \begin{aligned}\left\{\begin{matrix} 1,&n=1\\0,&\exist d,d^2\mid n\\(-1)^k,&\prod_{i=1}^kp_i=n \end{matrix}\right.\end{aligned}
一些常见的卷积：
- \mu\ast1=\varepsilon
- \mu\ast\text{id}=\varphi
- \mu\ast d=\mathbb1
一个变形（也是莫比乌斯反演的另一种理解方式）：
- f(n)=\sum_{d\mid n}g(d)\Leftrightarrow g(n)=\sum_{d\mid n}\mu(\frac nd)g(d)
  证：f=g\ast \mathbb1\Leftrightarrow g=f\ast\mu。
通过莫比乌斯反演，我们可以优化一些求和。

例 1：(重点是交换和式的过程（第 3 步到第 4 步）)
\begin{aligned} \sum_{i=1}^n\sum_{j=1}^m[\gcd(i,j)=k] &=\sum_{i=1}^n\sum_{j=1}^m[k\mid i][k\mid j][\gcd(\frac ik,\frac jk)=1]\\ &=\sum_{i=1}^{\lfloor \frac nk\rfloor}\sum_{j=1}^{\lfloor \frac mk\rfloor}[\gcd(i,j)=1]&(k在1\sim n中的倍数有\lfloor \frac nk\rfloor个)\\ &=\sum_{i=1}^{\lfloor \frac nk\rfloor}\sum_{j=1}^{\lfloor \frac mk\rfloor}\sum_{d\mid i,d\mid j}\mu(d)&(\varepsilon=\mu\ast\mathbb1)\\ &=\sum_{d=1}^{\min(\lfloor \frac nk\rfloor,\lfloor \frac mk\rfloor)}\mu(d)\sum_{i=1}^{\lfloor \frac nk\rfloor}[d\mid i]\sum_{j=1}^{\lfloor \frac mk\rfloor}[d\mid j]&(只有可以整除i,j的d才能计入答案)(交换求和，是数论的重要trick)\\ &=\sum_{d=1}^{\min(\lfloor \frac nk\rfloor,\lfloor \frac mk\rfloor)}\mu(d)\lfloor \frac n{kd}\rfloor\lfloor \frac m{kd}\rfloor&(显然这样的i,j有\lfloor \frac n{kd}\rfloor,\lfloor \frac m{kd}\rfloor个，换句话说就是求d的倍数)\\ \end{aligned} $$ d(i\times j)=\sum_{x\mid i}\sum_{y\mid j}[\gcd(x,y)=1] $$ 实质是枚举 $i,j$ 的因子，$\gcd (x,y)=1$ 是为了防止 $x,y$ 和另一对 $\frac x{\gcd(x,y)},\frac y{\gcd(x,y)}$ 重复。 #### 杜教筛：可以在 $\mathcal O(n^{\frac34})$ 的时间内求出积性函数前缀和。要求积性函数 $f$ 的前缀和我们定义 $S(n)=\sum_{i=1}^nf(i)$，再选取一个合适的积性函数 $g(n)$。我们考虑 $(f\ast g)=h$ 的前缀和： $$ \begin{aligned} \sum_{i=1}^nh(i)&=\sum_{i=1}^n\sum_{d\mid i}g(d)f(\frac id)\\ &=\sum_{d=1}^ng(d)\sum_{i=1}^n[d\mid i]f(\frac id)\\ &=\sum_{d=1}^ng(d)\sum_{i=1}^{\lfloor\frac nd\rfloor}f(i)\\ &=\sum_{d=1}^ng(d)S(\lfloor\frac nd\rfloor)\\ \end{aligned} $$ 则有： $$ \begin{aligned} g(1)S(n)&=\sum_{d=1}^ng(d)S(\lfloor\frac nd\rfloor)-\sum_{d=2}^ng(d)S(\lfloor\frac nd\rfloor)\\ &=\sum_{i=1}^nh(i)-\sum_{d=2}^ng(d)S(\lfloor\frac nd\rfloor)\\ \end{aligned} $$ 因此我们只需选取一个合适的、可以容易预处理 $h,g$ 前缀和的 $g$ 即可。另外如果先筛出前 $n^{\frac 23}$ 个数，复杂度可以优化到 $\mathcal O(n^{\frac23})$。杜教筛需配合数论分块、记忆化搜索使用。例题 1（[P4213 【模板】杜教筛](https://www.luogu.com.cn/problem/P4213)）：求 $$ \sum_{i=1}^n\varphi(i)\\ \sum_{i=1}^n\mu(i) $$ 我们直接用 $\mathbb1$ 卷，$\varphi$ 卷出来是 $\text{id}$，$\mu$ 卷出来是 $\varepsilon$，于是代码就出来了。 ```cpp #include<bits/stdc++.h> using namespace std; #define int long long const int N = 1700000 + 10; int read(){ int x; scanf("%lld",&x); return x; } int phi[N],mu[N]; bitset<N>vis; int p[N],tot; void init(){ phi[1]=1; mu[1]=1; for(int i=2;i<=N-10;i++){ if(!vis[i]) p[++tot]=i,phi[i]=i-1,mu[i]=-1; for(int j=1;j<=tot&&i*p[j]<=N-10;j++){ vis[i*p[j]]=true; if(i%p[j]==0){ phi[i*p[j]]=p[j]*phi[i]; mu[i*p[j]]=0; break; }else{ phi[i*p[j]]=(p[j]-1)*phi[i]; mu[i*p[j]]=-mu[i]; } } } for(int i=2;i<=N-10;i++) { phi[i]=phi[i]+phi[i-1]; mu[i]=mu[i]+mu[i-1]; } } unordered_map<int,int>ans_phi,ans_mu; int getphi(int n){ if(n<=N-10) return phi[n]; if(ans_phi[n]) return ans_phi[n]; int res=n*(n+1)/2; for(int l=2,r;l<=n;l=r+1) { r=n/(n/l); res-=(r-l+1)*getphi(n/l); } return ans_phi[n]=res; } int getmu(int n){ if(n<=N-10) return mu[n]; if(ans_mu[n]) return ans_mu[n]; int res=1; for(int l=2,r;l<=n;l=r+1) { r=n/(n/l); res-=(r-l+1)*getmu(n/l); } return ans_mu[n]=res; } signed main(){ init(); int t=read(); while(t--){ int n=read(); printf("%lld %lld\n",getphi(n),getmu(n)); } return 0; } ``` 这道题的一些细节： - 预处理筛出前 $O(n^{\frac 23})$ 的数。 - 开 `long long`，不然只有 $\texttt{10pts}$。 - 预处理用数组，记忆化搜索用 `unordered_map`。 - 不要忘记数论分块，不然只有 $\texttt{30pts}$。 - 减号不要写成加号。 - 要给 $\varphi(1),\mu(1)$ 赋初值 $1
Lucas 定理：

若 p 为质数，则有结论
\binom nm\equiv\binom{\lfloor\frac np\rfloor}{\lfloor\frac mp\rfloor}\binom{n\text{ mod }p}{m\text{ mod }p}\pmod p
P2480 [SDOI2010] 古代猪文 - 洛谷

求
g^{\sum \limits_{d\mid n}\binom{n}{d}}\text{ mod }999911659
用欧拉定理，原式化为
g^{\sum \limits_{d\mid n}\binom{n}{d}\text{ mod }999911658}\text{ mod }999911659
有
999911658=2\times3\times4679\times35617
对每个质数求解组合数，然后用 \texttt{CRT} 合并，用快速幂求答案。
```
#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int MOD=999911659;
int mod[5]={0,2,3,4679,35617},a[5];
int n,g;
int qp(int a,int b,int p){
    int ans=1;
    while(b){
        if(b&1) ans=ans*a%p;
        a=a*a%p;
        b>>=1;
    }
    return ans;
}
int inv(int a,int p){
    return qp(a,p-2,p);
}
int jc[36000],jc_inv[36000];
void pre(int p){
    jc[0]=1;
    for(int i=1;i<p;i++) jc[i]=jc[i-1]*i%p;
    jc_inv[p-1]=inv(jc[p-1],p);
    for(int i=p-2;i>=0;i--) jc_inv[i]=jc_inv[i+1]*(i+1)%p;
}
int C(int n,int m,int p){
    if(m>n) return 0;
    return jc[n]*jc_inv[m]%p*jc_inv[n-m]%p;
}
int lucas(int n,int m,int p){
    if(m==0) return 1;
    return C(n%p,m%p,p)*lucas(n/p,m/p,p)%p;
}
void exgcd(int a,int b,int&x,int&y){
    if(!b) x=1,y=0;
    else exgcd(b,a%b,y,x),y-=a/b*x;
}
int crt(){
    int M=MOD-1,ans=0;
    for(int i=1;i<=4;i++){
        int m=M/mod[i];
        int x,y;
        exgcd(m,mod[i],x,y);
        x=(x%mod[i]+mod[i])%mod[i];
        ans=(ans+a[i]*m%M*x%M)%M;
    }
    return ans;
}
signed main(){
    cin>>n>>g;
    if(g==MOD){
        cout<<0;
        return 0;
    }
    for(int k=1;k<=4;k++){
        int p=mod[k];
        pre(p);
        for(int i=1;i*i<=n;i++){
            if(n%i==0){
                a[k]=(a[k]+lucas(n,i,p))%p;
                if(i*i!=n) a[k]=(a[k]+lucas(n,n/i,p))%p;
            }
        }
    }
    int p=crt();
    cout<<qp(g,p,MOD);
    return 0;
}
```

图论部分

树论

树剖

利用线段树在树上进行加值求值求 LCA 等操作，是树上问题的常用帮手

struct node{
    int l,r;
    long long z;
    long long lz_add;
}t[800010];

void built(int l,int r,int id){
    t[id].l=l;
    t[id].r=r;
    t[id].lz_add=0;
    if(l==r){
        t[id].z=wt[l]%mod;
        return;
    }
    int mid=(l+r)/2;
    built(l,mid,id*2);
    built(mid+1,r,id*2+1);
    t[id].z=(t[id*2].z+t[id*2+1].z)%mod;
}

void pushdown(int id){
    if(t[id].lz_add!=0){
        t[id*2].lz_add=(t[id*2].lz_add+t[id].lz_add)%mod;
        t[id*2+1].lz_add=(t[id*2+1].lz_add+t[id].lz_add)%mod;
        t[id*2].z=(t[id*2].z+t[id].lz_add*(t[id*2].r-t[id*2].l+1))%mod;
        t[id*2+1].z=(t[id*2+1].z+t[id].lz_add*(t[id*2+1].r-t[id*2+1].l+1))%mod;
        t[id].lz_add=0;
    }
}

void add_range(int x,int y,int k,int id){
    int L=t[id].l,R=t[id].r;
    if(x<=L&&y>=R){
        t[id].lz_add=(t[id].lz_add+k)%mod;
        t[id].z=(t[id].z+k*(R-L+1))%mod;
        return;
    }
    pushdown(id);
    int mid=(L+R)/2;
    if(x<=mid)add_range(x,y,k,id*2);
    if(y>mid)add_range(x,y,k,id*2+1);
    t[id].z=(t[id*2].z+t[id*2+1].z)%mod;
}

long long fd(int x,int y,int id){
    int L=t[id].l,R=t[id].r;
    if(x<=L&&y>=R)return t[id].z;
    pushdown(id);
    int mid=(L+R)/2;
    long long ans=0;
    if(x<=mid)ans=(ans+fd(x,y,id*2))%mod;
    if(y>mid)ans=(ans+fd(x,y,id*2+1))%mod;
    return ans;
}

inline void dfs1(int x,int f,int deep){
    dep[x]=deep;
    fa[x]=f;
    siz[x]=1;
    int maxson=-1;
    for(int i=beg[x];i;i=nex[i]){
        int y=to[i];
        if(y==f)continue;
        dfs1(y,x,deep+1);
        siz[x]+=siz[y];
        if(siz[y]>maxson)son[x]=y,maxson=siz[y];
    }
}

inline void dfs2(int x,int topf){
    id[x]=++cnt;
    wt[cnt]=w[x];
    top[x]=topf;
    if(!son[x])return;
    dfs2(son[x],topf);
    for(int i=beg[x];i;i=nex[i]){
        int y=to[i];
        if(y==fa[x]||y==son[x])continue;
        dfs2(y,y);
    }
}

inline int qRange(int x,int y){
    int ans=0;
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]])swap(x,y);
        ans=(ans+fd(id[top[x]],id[x],1))%mod;
        x=fa[top[x]];
    }
    if(dep[x]>dep[y])swap(x,y);
    ans=(ans+fd(id[x],id[y],1))%mod;
    return ans;
}

inline void updRange(int x,int y,int k){
    k%=mod;
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]])swap(x,y);
        add_range(id[top[x]],id[x],k,1);
        x=fa[top[x]];
    }
    if(dep[x]>dep[y])swap(x,y);
    add_range(id[x],id[y],k,1);
}

inline int qSon(int x){
    return fd(id[x],id[x]+siz[x]-1,1);
}

inline void updSon(int x,int k){
    add_range(id[x],id[x]+siz[x]-1,k,1);
}

圆方树：

常用于解决仙人掌类问题，即无自环无重边无向连通任意一条边最多属于一个简单环的图，构造方法为在每个点双构建一个方点，方点与点双内的点连边，其余边舍弃，显然这样的图也是没环的，利用方点存点双信息，圆点存自己信息

仙人掌

void tarjan(int u,int fa){
    bool ca=false;
    dfn[u]=low[u]=++tim;st.push(u);
    for(int i=h[u];i;i=edge[i].ne){
        int v=edge[i].e;
        if(v==fa) continue;
        if(!dfn[v]){
            tarjan(v,u);
            low[u]=min(low[u],low[v]);
            if(low[v]<dfn[u]){
                if(ca){isc=false;return ; }
                ca=true; 
            }
        }
        else{
            low[u]=min(low[u],dfn[v]);
            if(dfn[v]<dfn[u]){
                if(ca){isc=false;return ; }
                ca=true; 
            }
        }
    }
    if(low[u]==dfn[u]){
        scc_cnt++;int y;
        do{
            y=st.top();st.pop();
            id[y]=scc_cnt;
        }while(y!=u);
    }
}

欧拉路径：

欧拉回路 (路径) 是一条遍历所有边恰好一次的回路 (路径)，点可以重复经过。

有向图存在欧拉回路的充要条件是每个点入度等于出度且图连通。

无向图存在欧拉回路的充要条件是每个点度数为偶数且图连通。

求解可用 dfs

void dfs(int u){
    for(int i=h[u];i;i=edge[i].ne){
        if(flag[i]) continue;
        flag[i]=flag[i^1]=true;
        int v=edge[i].e;
        dfs(v);
        if(ha[u]<ha[v]) ans[i/2]=0;
        else ans[i/2]=1;
    }
}

常言道如果一道题有点莫名其妙，那它很有可能是用欧拉路径来写

Point and Segment

题意：给定 n 条线段 [l_i,r_i], 然后给这些线段红蓝染色，求最后直线上上任意一个点被蓝色及红色线段覆盖次数之差的 ** 绝对值不大于 1 **。

由于是计算绝对值之差，把蓝色看成 1，红色看作 - 1，原题就被转换为了

给定 n 个区间 [l_i,r_i]，你可以选择区间并把区间的所有元素 + 1 或 - 1，使得绝对值不大于 1

由于是区间操作，考虑使用差分解决，[l_i,r_i] 的 + 1 操作显然就是在 l_i 处 + 1，r_i+1 处 - 1，反之同理，这样一个可正可反的，只有 + 1-1 的操作不由地想到了无向边，入的即为 +，出的即为 -，偶数度的点都可以变为 0，跑一遍欧拉回路看边的方向即可知道一种解，奇数度的点显然无法变为 0，且妨碍到了欧拉回路，然而奇数度的点的个数一定是偶数个的，所以考虑把他们两两相连，为了满足题意，把这些点单独拎出来后相邻的两个点差分必须是 - 1，+1，故虚拟边连向相邻的两个点，如果这条边由 A->B，则 B 多加了 1，即为 - 1，A 少加了 1，即为 + 1, 满足题意

由此可见，欧拉回路的题难的不在算法而在建模，转换

二分图：

二分图判定：

使用 dfs01 染色即可，当染色出现矛盾时则说明这不是个二分图

也可以使用 tarjan 判断奇环，若存在奇环则不是二分图

二分图最大匹配：

虽然可以使用网络流算法解决，但~~没通网~~不会网络流或者觉得太麻烦也可以使用~~野蛮人~~匈牙利算法解决，具体地，可以尝试暴力尝试匹配

bool match(int x){
    for(int i=n+1;i<=n+m;i++){
        if(t[x][i]&&!vis[i]){
            vis[i]=true;
            if(!p[i]||match(p[i])){p[i]=x;return true;} 
        }
    }
    return false;
}
int hun(){
    int ans=0;
    for(int i=1;i<=n;i++){
        memset(vis,false,sizeof(vis));
        if(match(i)) ans++;
    }
    return ans;
}

网络流：

前言：网络流算法学习不难，难的是建模

下文中若未作特殊声明，S 为源点，T 为汇点

最大流：

** 主要解决问题：** 常用于解决二分图最大问题，具体地，S--> 左端 --> 右端 -->T 连边，左右点之间的连边代表可以匹配，流量为一，最大流即为最大匹配，除了二分图匹配问题，其还能解绝最大流量类问题，需依据不同题意建模

最小割：

引理：将图建成网络，代价 c 设置成对应的容量上限，跑该网络的最大流就是原图的最小割。

反证法：若并非最小割那么一定存在一条路径连通 S 和 T, 就一定存在一条增广路使流量变大，不符合最大流定义

** 主要解决问题：** 最小割主要用于解决二分图最大权独立集问题，集合划分模型，最大权闭合子图问题；

在方格图中，使用对偶图（以面为点，边顺时针旋转 90°）最短路也是一种求最小割的方法，且复杂度优秀

费用流：

即最小费用最大流，使用 dinic 算法，将 bfs 改为 spfa 即可

** 主要解决问题：** 分配收益问题

看似问题少，实则细分下来也有不少小点

技巧部分：

1. 建图技巧

多源多汇：建立超级汇点超级源点

无限之环

点内流量 / 费用限制：拆点为入点出点，限制在连边中体现

[晨跑]([P2153 [SDOI2009] 晨跑 - 洛谷](https://www.luogu.com.cn/problem/P2153) )

利用题目性质优化建图：边数过多时，考虑利用性质优化建图

[卡片]([P2065 [TJOI2011] 卡片 - 洛谷](https://www.luogu.com.cn/problem/P2065) )

当题目有时间限制时，考虑依时间分层 / 分类建图

[家园 / 星际转移问题]([P2754 [CTSC1999] 家园 / 星际转移问题 - 洛谷](https://www.luogu.com.cn/problem/P2754) )

2. 模型

1. 求二分图最大权独立集

同样的 S--> 左端 --> 右端 -->T 连边，中间连 INF, 两边连权值

在网格图中，可以黑白染色来区分连接源点汇点

引理：二分图最大权独立集 = 权值 - 最小割

由此可求出二分图最大权独立集

方格取数问题

2. 集合划分模型：

n 个物品，要划分到 AB 两个集合中，分入某个集合有代价，某些物品被划分到不同区间还有代价，分到相同集合也有代价，求最小代价

对于单独的代价，向集合建一条流量为代价的边

对于不同区间的代价，两点间连一条流量为代价的边

对于相同区间的代价，建立新点向包含点建立流量为 INF 的边，新点向集合连一条流量为代价的边

文理分科

3. 最大权闭合子图

每个点有可负点权，求满足 \forall u \in A\ \ \ (u,v)\in E,v \in A 的最大权子图

由于对于非负权点，需要选择他前面的负权点才可选到，选择负权相当于舍弃权值，不选非负权也是舍弃权值

它能到达的所有点权为负的点连边，再从 s 向点权非负的点分别连边，点权为负的点向 t 连边，那么考虑一种选择对应了什么：

对于一个点权非负的点，要么干脆不选它，要是选了就得舍弃它能到达的所有点权为负的点的点权；

如果不选这个点，就理解成割掉 s 到它的边，而舍弃一个右边的点就理解成割掉它到 t 的边，由此，一种选择对一种割；

将 s 到点权非负的点的边的代价设为其权值，点权为负的点到 t 的边的代价设为其权值的绝对值，其余边代价为 INF，

用点权非负的所有点的权值和减去 s 到 t 的最小割即为答案。

植物大战僵尸

4. 对偶图最短路：

即建立对偶图跑最短路，以面为点，边顺时针旋转 90°，权值不变，建立对偶图，利用多源多汇的技巧建图，跑最短路即可

海拔

5. 最小割树：

当有多组询问两点间最小割且不带修时大概率就是最小割树了

引理：两点之间只有 n 种本质不同的最小割。因此一定存在一棵树，满足树上两点的最小

割等于原图上两点的最小割

具体地，为了求出这样的一颗树采用分治算法，不断以两点 S,T 为源汇跑最小割把集合分开，S 与 T 间建立起最小割大小的边

最小割树

void built(int ll,int rr){
    if(ll>=rr) return ;
    s=v[ll];t=v[ll+1];
    memcpy(edge,EDGE,sizeof(EDGE));
    ans=dinic();
    vec[s].push_back(t);vec[t].push_back(s);
    w[s].push_back(ans);w[t].push_back(ans);
    int ltop=ll,rtop=rr;
    for(int i=ll;i<=rr;i++) if(dis[v[i]]!=INF) tmp[ltop++]=v[i];else tmp[rtop--]=v[i];
    for(int i=ll;i<=rr;i++) v[i]=tmp[i];
    built(ll,ltop-1);
    built(rtop+1,rr);
}
int Get(){
    memset(dis,0,sizeof(dis));
    queue<int> q;q.push(s);dis[s]=INF;
    while(!q.empty()){
        int u=q.front();q.pop();
        for(int i=0;i<vec[u].size();i++){
            int v=vec[u][i];
            if(!dis[v]){
                dis[v]=min(dis[u],w[u][i]);
                if(v==t) return dis[v];
                q.push(v);
            }
        }
    }
    return dis[t];
}

6. 分配问题：

有 n 件工作要分配给 n 个人做。第 i 个人做第 j 件工作产生的效益为 c_{i,j}。试设计一个将 n 件工作分配给 n 个人做的分配方案，使产生的总效益最小或最大。

分配问题

板子部分

dinic

bool bfs(){
    for(int i=1;i<=n;i++) dis[i]=INF;
    queue<int> q;
    q.push(s);
    dis[s]=0;
    now[s]=h[s];
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int i=h[u];i;i=edge[i].ne){
            int v=edge[i].e;
            if(edge[i].w>0&&dis[v]==INF){
                q.push(v);
                now[v]=h[v];
                dis[v]=dis[u]+1;
                if(v==t) return 1;
            }
        }
    }
    return 0;
}
int dfs(int x,long long sum){
    if(x==t) return sum;
    long long k,tmp=0;
    for(int i=now[x];i&&sum;i=edge[i].ne){
        now[x]=i;
        int v=edge[i].e;
        if(edge[i].w>0&&dis[v]==dis[x]+1){
            k=dfs(v,min(sum,edge[i].w));
            if(k==0) dis[v]=INF;
            edge[i].w-=k;
            edge[i^1].w+=k;
            tmp+=k;sum-=k;
        }
    }
    return tmp;
}
void dinic(){
    while(bfs()){
    ans+=dfs(s,INF)
    }
}

HLPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int INF=0x3f3f3f3f;
int n,m,s,t;
struct node{
    int e,ne,val;
}edge[500000];
int h[100000],tt=1;
void add(int u,int v,int val){
    edge[++tt].e=v,edge[tt].ne=h[u],edge[tt].val=val,h[u]=tt;
    edge[++tt].e=u,edge[tt].ne=h[v],edge[tt].val=0,h[v]=tt;
}
int hi[100000],gap[100000],E[100000];
bool flag[100000];
void bfs(){
    memset(hi,0x3f,sizeof(hi));
    queue<int> q;q.push(t);
    hi[t]=0;++gap[0];
    while(!q.empty()){
        int u=q.front();q.pop();
        for(int i=h[u];i;i=edge[i].ne){
            int v=edge[i].e,val=edge[i].val;
            if(val==0&&hi[v]==0x3f3f3f3f3f3f3f3f){
                hi[v]=hi[u]+1;
                ++gap[hi[v]];
                q.push(v);
            }
        }
    }
}
struct cmp{
    inline bool operator()(const int x,const int y){
        return hi[x]<hi[y];
    }
};
priority_queue<int,vector<int>,cmp> pq;
void id(int x){
    --gap[h[x]];
    if(!gap[h[x]]){
        for(int i=1;i<=n;i++){
            if(hi[i]>hi[x]&&i!=s&&i!=t){
                --gap[hi[i]];
                hi[i]=n+1;
            }
        }
    }
    hi[x]=5000;
    for(int i=h[x];i;i=edge[i].ne){
        int v=edge[i].e,val=edge[i].val;
        if(val>0&&hi[v]+1<hi[x]){
            hi[x]=hi[v]+1;
        }
    }
    ++gap[hi[x]];
}
void HLPP(){
    bfs();
    hi[s]=n;
    for(int i=h[s];i;i=edge[i].ne){
        int v=edge[i].e,val=edge[i].val;
        if(val>0){
            E[v]+=val;
            edge[i].val-=val,edge[i^1].val+=val;
        }
        if(v!=t&&v!=s&&!flag[v]){
            pq.push(v);flag[v]=true;
        }
    }
    while(!pq.empty()){
        int u=pq.top();pq.pop();
        flag[u]=false;
        for(int i=h[u];i;i=edge[i].ne){
            int v=edge[i].e,val=edge[i].val;
            if(val>0&&hi[u]==hi[v]+1){
                int f=min(val,E[u]);
                E[u]-=f,E[v]+=f;edge[i].val-=f,edge[i^1].val+=f;
                if(!flag[v]&&v!=s&&v!=t){
                    pq.push(v);flag[v]=true;
                }
            }
            if(!E[u]) break;
        }
        if(E[u]!=0){
            id(u);
            pq.push(u);flag[u]=1;
        }
    }
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>m>>s>>t;
    for(int i=1,x,y,z;i<=m;i++){
        cin>>x>>y>>z;
        add(x,y,z);
    }
    HLPP();
    cout<<E[t];
    return 0;
}

数据结构部分

**0 / 1 trie:** 用于解决位运算问题（尤其异或）[最长异或路径](P4551 最长异或路径 - 洛谷 )

线段树合并：序列合并类的题雨天的尾巴

线段树合并的方式多种多样，但本质上是合并相同节点，复制未有节点

李超线段树：维护凸包用，函数必须满足只有一个交点，否则李超线段树正确性无法被保证

struct line{
    double k,b;
}p[400001];
int s[414514];
int cmp(double x,double y){
    if(x-y>1e-9) return 1;
    if(y-x>1e-9) return -1;
    return 0;
}
inline double js(int id,int x){
    return p[id].k*x+p[id].b;
}
inline void add(int x0,int yy0,int x1,int yy1){
    if(x0==x1) p[++cnt].k=0,p[cnt].b=max(yy0,yy1);
    else p[++cnt].k=1.0*(yy1-yy0)/(x1-x0),p[cnt].b=yy0-p[cnt].k*x0;
}
void upd(int root,int L,int R,int u) {
    int &v=s[root],mid=(L+R)>>1;
    if(v==0){v=u;return;}
    double lu=js(u,L),ru=js(u,R);
    double lv=js(v,L),rv=js(v,R);
    if(cmp(lu,lv)>0&&cmp(ru,rv)>0) {v=u;return;}
    if(cmp(lu,lv)<=0 &&cmp(ru,rv)<=0) return;
    int bmid=cmp(js(u,mid),js(v,mid));
    if(bmid==1||(bmid==0&&u<v)) swap(u,v);
    if(cmp(js(u,L),js(v,L))>0||(cmp(js(u,L),js(v,L))==0&&u<v)) upd(root<<1, L, mid, u);
    if(cmp(js(u,R),js(v,R))>0||(cmp(js(u,R),js(v,R))==0&&u<v)) upd(root<<1|1, mid+1, R, u);
}
void update(int root,int L,int R,int l,int r,int u){
    if(l<=L&&R<=r){
        upd(root,L,R,u);
        return ;
    }
    int mid=(L+R)>>1;
    if(l<=mid) update(root<<1,L,mid,l,r,u);
    if(mid<r) update(root<<1|1,mid+1,R,l,r,u);
}
pair<double,int> pmax(pair<double,int> x,pair<double,int> y){
    if(cmp(x.first,y.first)==-1) return y;
    if(cmp(x.first,y.first)==1) return x;
    else return x.second<y.second?x:y;
}
pair<double,int> query(int root,int L,int R,int x){
    if(R<x||x<L) return {-1e18,0};
    int mid=(L+R)>>1;
    double ans=js(s[root],x);
    if(L==R) return {ans,s[root]};
    return pmax({ans,s[root]},pmax(query(root<<1,L,mid,x),query(root<<1|1,mid+1,R,x)));
}

根号算法部分

分块：

暴力这 \sqrt{n} 块

序列分块：

将一个序列分成 B 块，修改的同时维护块内性质，查询时若在块内则暴力，否则整块利用先前的维护求值，散块暴力求解，具体块的大小需根据题目修改，但大部分都是 \sqrt{n} 的大小

例题：蒲公英

题意概括：给出长度为 n 的序列，询问 [l,r] 的众数

以此题为例，细讲如何推导最佳块大小，维护前缀和，然而数的种类太多，空间无法承受，于是分块储存前缀和，这里没有修改操作，维护，储存前缀和，整块内众数，数字出现位置即可，区间众数只会出现在整块众数与散块中的数中，预处理是 (n/B)^2 的，询问是 q \times(2\times B \times \log (此数字出现个数)) 的，由于值域大个数少 log 几乎可以当作常数看待，总复杂度是 \frac{n^2}{B^2} +2qB 的发现 q 和 n 差不多大小，把 q 当作 n 看待，利用基础不等式可以推得 B=\sqrt[3]{n} 是优秀的，这里也可以取 B=\sqrt[3]{\frac{n}{2}} 但空间上有点紧；

莫队：

普通莫队：

有许多询问 [l,r], 且对于有交集的地方的处理是相同的，则可以使用莫队来处理，莫队的基础是双指针法，本质上相当于是为了构造一条经过所有点（l,r）的路径，每次只能移动一个单位，使得路径长度尽可能短。

对 l 进行分块按照块顺序为第一关键字，r 为第二关键字进行排序（可以进行奇偶优化），移动距离约为（qB+\frac{n^2}{B}）同样基本不等式取（\frac{n}{\sqrt{q}}）即可

附奇偶优化 cmp

bool cmp(node a,node b){
    int block_a=a.l/siz;
    int block_b=b.l/siz;
    if(block_a!=block_b)return block_a<block_b;
    return (block_a&1)?a.r<b.r:a.r>b.r;
}

[小 Z 的袜子]([P1494 [国家集训队] 小 Z 的袜子 - 洛谷](https://www.luogu.com.cn/problem/P1494) )

莫队二次离线：

第一次离线莫队，第二次离线做扫描线，和普通莫队的区别是贡献部分用扫描线的方法计算，此算法适用于

**「区间计算有多少满足条件点对」** 问题，具体的

[Yuno loves sqrt technology II]([P5047 [Ynoi2019 模拟赛] Yuno loves sqrt technology II - 洛谷](https://www.luogu.com.cn/problem/P5047) )

区间查询逆序对数

动态规划部分

数据结构优化 dp

线段树优化 dp: 士兵

李超线段树优化 dp:[Building Bridges]([P4655 [CEOI 2017] Building Bridges - 洛谷](https://www.luogu.com.cn/problem/P4655) )

这两类的区别主要体现在 dp 式子上，若是 1D 的式子则大概率线段树，2D 的式子则大概率李超线段树

状压 dp

[寿司晚宴]([P2150 [NOI2015] 寿司晚宴 - 洛谷](https://www.luogu.com.cn/problem/P2150) )

把 dp 的选与不选压缩为 01，构造二进制数进行状态压缩

DDP:

前置：

广义矩阵乘法：

对于 \oplus 和 \otimes 这两种运算，若有

\otimes$ 有交换律：$a \otimes b = b \otimes a
\otimes$ 有结合律：$(a \otimes b) \otimes c= a \otimes (b \otimes c)

则有广义矩阵乘法

常见的有 \oplus 是 +，\otimes 是 \times

jz operator *(const jz &x,const jz &y){
    jz z;
    for(int k=1;k<=sz;k++){
        for(int i=1;i<=sz;i++){
            for(int j=1;j<=sz;j++){
                z.a[i][j]=(z.a[i][j]+x.a[i][k]%mod*y.a[k][j]%mod)%mod;
            }
        }
    }
    return z;
}

```c++ jz operator *(const jz &x,const jz &y){ jz z; for(int i=1;i<=sz;i++) for(int j=1;j<=sz;j++) z.a[i][j]=INF; for(int k=1;k<=sz;k++) for(int i=1;i<=sz;i++) for(int j=1;j<=sz;j++) z.a[i][j]=min(z.a[i][j],x.a[i][k]+y.a[k][j]); return z; } ``` #### 解题：此类题需要将转移写成矩阵形式例如 [New Year and Old Subsequence](https://www.luogu.com.cn/problem/CF750E) 有 $$ \left\{\begin{array}{l} f_{i, 0}=\left\{\begin{array}{l} f_{i-1,0}+1\left(s_{i}=2\right) \\ f_{i-1,0}\left(s_{i} \neq 2\right) \end{array}\right. \\ f_{i, 1}=\min \left(\left\{\begin{array}{l} f_{i-1,1}+1\left(s_{i}=0\right) \\ f_{i-1,1}\left(s_{i} \neq 0\right) \end{array},\left\{\begin{array}{l} f_{i-1,0}\left(s_{i}=2\right) \\ \inf \left(s_{i} \neq 2\right) \end{array}\right)\right.\right. \\ f_{i, 2}=\min \left(\left\{\begin{array}{l} f_{i-1,2}+1\left(s_{i}=1\right) \\ f_{i-1,2}\left(s_{i} \neq 1\right) \end{array},\left\{\begin{array}{l} f_{i-1,1}\left(s_{i}=0\right) \\ \inf \left(s_{i} \neq 0\right) \end{array}\right)\right.\right. \\ f_{i, 3}=\min \left(\left\{\begin{array}{l} f_{i-1,3}+1\left(s_{i}=7 \text { or } s_{i}=6\right) \\ f_{i-1,3}\left(s_{i} \neq 7 \text { and } s_{i} \neq 6\right) \end{array},\left\{\begin{array}{l} f_{i-1,2}\left(s_{i}=1\right) \\ \inf \left(s_{i} \neq 1\right) \end{array}\right)\right.\right. \\ f_{i, 4}=\min \left(\left\{\begin{array}{l} f_{i-1,4}+1\left(s_{i}=6\right) \\ f_{i-1,4}\left(s_{i} \neq 6\right) \end{array},\left\{\begin{array}{l} f_{i-1,3}\left(s_{i}=7\right) \\ \inf \left(s_{i} \neq 7\right) \end{array}\right)\right.\right. \end{array}\right. $$ 可以转换为 $$ \left[ f_{i-1,0}\quad f_{i-1,1}\quad f_{i-1,2}\quad f_{i-1,3}\quad f_{i-1,4} \right] \times \left[ \begin{array}{ccccc} (s_i=2)?1:0 & (s_i=2)?0:\inf & \inf & \inf & \inf \\ \inf & (s_i=0)?1:0 & (s_i=0)?0:\inf & \inf & \inf \\ \inf & \inf & (s_i=1)?1:0 & (s_i=1)?0:\inf & \inf \\ \inf & \inf & \inf & (s_i=7\ or\ s_i=0)?1:0 & (s_i=7)?0:\inf \\ \inf & \inf & \inf & \inf & (s_i=6)?1:0 \\ \end{array} \right] $$ 用线段树维护即可如若想在树上使用该算法可以使用树剖 [保卫王国](https://www.luogu.com.cn/problem/P5024) ### 决策单调性优化 dp: $f_i= \min _{1\le j \le i}(w_{j,i})

若对于上述的 $w(l,r)

\forall l_1 \le l_2 \le r_1 \le r_2,w(l_1,r_1)+w(l_2,r_2) \le w(l_1,r_2)+w(l_2,r_1)

即交叉优于包含

则这个式子满足决策单调性，可以用分治或队列 \ 栈优化

队列 \ 栈优化诗人小 G

long double qpow(long double x,int p){
    if(!p) return 1.0;
    long double sum=x,ans=1;
    while(p){
        if(p&1) ans*=sum;
        p>>=1;sum*=sum;
    }
    return ans;
}
long double calc(int i,int j){
    return dp[j]+qpow((long double)abs(sum[i]-sum[j]+i-j-l-1),p);
}
 int find(int j,int i){
    int l=j+1,r=n+1;
    while(l<r){
        int mid=(l+r)>>1;
        if(calc(mid,j)>=calc(mid,i)) r=mid;
        else l=mid+1;
    }
    return l;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>T;
    while(T--){
        cin>>n>>l>>p;
        for(int i=1;i<=n;i++) 
            cin>>s[i],sum[i]=strlen(s[i]+1)+sum[i-1]+1;

        q[h=t=1]=0;
        for(int i=1;i<=n;i++){
            while(h<t&&k[h]<=i) h++;
            pre[i]=q[h];
            dp[i]=calc(i,q[h]);
            while(h<t&&k[t-1]>=find(q[t],i)) t--;
            k[t]=find(q[t],i);
            q[++t]=i;
        }

        if(dp[n]>1e18) cout<<"Too hard to arrange\n";
        else{
            cout<<(long long)dp[n]<<'\n';
            int stk[100007],top=0;
            for(int i=n;i;i=pre[i]) stk[++top]=i;
            for(int i=top,last=0;i>=1;i--){
                for(int j=last+1;j<stk[i];j++)
                    cout<<s[j]<<' ';
                cout<<s[stk[i]]<<'\n';
                last=stk[i];
            }
        }
        cout<<"--------------------\n";
    }
    return 0;
}

分治优化灯塔

void so(int l,int r,int L,int R){
    if(l>r) return ;
    int mid=l+r>>1,opt=L;
    for(int i=L+1;i<=min(mid,R);i++) if(js(mid,opt)<js(mid,i)) opt=i;
    p[mid]=max(p[mid],js(mid,opt));
    so(l,mid-1,L,opt);
    so(mid+1,r,opt,R); 
}

wqs 二分

当出现 2D 的转移式子时，我们不仅能用李超线段树维护凸壳，wqs 也是一种在解决恰有 k 个物品的最大 \ 最小价值问题时的方法

若恰好 x 个物品的价值 f(x) 是一个下凸函数，则可以使用，我们为每多选一个物品加一个惩罚，惩罚越大选用物品的个数就越少，惩罚越小就越多，因此我们可以不断调整这个惩罚来逼近 k

忘情

bool check(int mid){
    memset(f,0x3f,sizeof(f));
    memset(g,0,sizeof(g));
    f[0]=0,opt[1]=0;
    int l=1,r=1;
    for(int i=1;i<=n;i++){
        while (l<r&&(Y(opt[l+1])-Y(opt[l]))/(s[opt[l+1]]-s[opt[l]])<2*s[i]) l++;
        f[i]=f[opt[l]]+(s[i]-s[opt[l]]+1)*(s[i]-s[opt[l]]+1)+mid;
        g[i]=g[opt[l]]+1;
        while (l<r&&(long double)(Y(opt[r-1])-Y(opt[r]))/(s[opt[r-1]]-s[opt[r]])>(long double)(Y(opt[r-1])-Y(i))/(s[opt[r-1]]-s[i])) r--;
        opt[++r]=i;
    }
    return g[n]<=m;
}
signed main(){
    int l=-1e18,r=1e18,ans=0;
    while(l<=r){
        int mid=(l+r)>>1;
        if(check(mid)) r=mid-1,ans=mid;
        else l=mid+1;
    }
    check(ans);
    cout<<f[n]-m*ans; 
    return 0;
}

注意答案不要忘记减去惩罚

插入 dp

插入类 dp 核心在于以某种顺序插入元素，这样可以确保前面元素的限制小于后面的，从而简化了状态转移的复杂性

这类 dp 的状态设计为插入 i 个元素，已形成 j 个连续段

转移通常为

新开一段
合并两段
放在某端边缘

对于左右端点需要特判

字符串算法

Manacher

Manacher 算法是一种用于求解单串回文结构的算法，可以求出以位置 i 为中心的最长回文串的半径长度，这个信息，对于处理回文串问题有非常大帮助。

具体地，将 s 的相邻两个字符之间添一个相同的罕见字符，

考虑用 p[1], · · · , p[i − 1] 递推 p[i]。定义 mr 表示之前的 i + p[i] − 1 的最大值 (即最靠右的回文串)。同时记录这个回文中心为 mid (如果有多个，记录最靠右的)。

考虑当前位置 i：

如果 i ≤ mr，则设置初值为 p[i] = min(p[mid ∗ 2 − i], mr − i + 1)。
否则设置初值为 p[i] = 1。

之后暴力向两侧扩展 p[i]，并更新 mid 和 mr。

void build(){
    scanf("%s",c+1),n=strlen(c+1),s[++cnt]='~',s[++cnt]='#';
    for(int i=1;i<=n;i++) s[++cnt]=c[i],s[++cnt]='#';
    s[++cnt]='!';
}
void solve(){
    for(int i=2;i<=cnt-1;i++){
        if(i<=mr) p[i]=min(p[mid*2-i],mr-i+1);
        else p[i]=1;
        while(s[i+p[i]]) ++p[i];
        if(i+p[i]>mr) mr=i+p[i]-1,mid=i;
        ans=max(ans,p[i]);
    }
    cout<<ans-1;
}

分治算法

线段树分治

Bipartite Checking

从这个线段树分治板子题，从头整理一下线段树分治的一些重点。

首先看到本题，如果只有添加边一种操作的话，显然是可以用扩展域并查集维护的，如果不会可以翻到本文最后面有讲。

但是本题有删除边的操作，这就不能只用并查集维护了。

我们考虑一个 O(n^2) 的暴力（设 n,m 同阶），对每一个询问，找到有哪些边在这个询问时是存在的，然后直接在空并查集上加边，最后判断是否为二分图。

考虑这个暴力不足的地方：由于操作是对一个时间区间都存在，有一些边在下一个询问中仍然是存在的，但是我们将其全部删掉了。我们的并查集虽然不能支持删除边，但是可以撤销！如果我们知道相对下一个询问，我们需要撤销哪些边，再加上哪些边，是不是可以优化复杂度呢？

线段树分治的思想

我们对时间（询问）建立一颗线段树，树的节点存的信息是【覆盖了这个区间的操作】。

考虑遍历整颗线段树，维护一颗可撤销并查集。当进入一个线段树的子节点时，在并查集上添加覆盖这个区间的边。然后继续递归子节点，直到叶子节点（对应的就是一个询问），统计对应的答案。回溯时，将这个节点加的边在并查集上撤销。

这样，递归到每一个叶子节点时，并查集中的边都是这个询问的完整状态。

分析复杂度，遍历线段树的时间是 O(n\log n) 的，总共 O(n) 个操作，每一个操作在线段树上最多覆盖 \log n 个节点，可撤销并查集由于不能使用路径压缩，所以按秩合并的复杂度是 O(\log n) 的，维护操作的复杂度是 O(n\log^2n) 的。

这就是线段树分治。

看到什么应该想到线段树分治？

多个操作，每一个操作的影响范围是一个区间（时间区间，询问区间）。
多个询问，询问（某个时间时，某个操作后的）答案。

比如本题：操作为删除或者添加边，也就是说一条边的影响范围是一个区间。同时在每一次操作后求答案（是否为二分图）。

实现

struct BCJ
{
    int n;
    int fa[200010];
    int dep[200010];
    void init(int x){
        n=x;
        for(int i=1;i<=2*n;i++){
            fa[i]=i;
            dep[i]=1;
        }
    }
    int find(int x){
        return x==fa[x]?x:find(fa[x]);
    }
    void merge(int x,int y,stack<int>&sta){
        x=find(x),y=find(y);
        if(x==y)return;
        if(dep[x]<dep[y])swap(x,y);
        fa[y]=x;
        dep[x]=max(dep[x],dep[y]+1);
        sta.push(y);
    }
    void roll_back(stack<int>&sta){
        while(!sta.empty()){
            int x=sta.top();
            sta.pop();
            fa[x]=x;
        }
    }
}bcj;
struct EDGE{
    int x,y;
}edge[200010];
vector<int> tr[800010];
int n,m;
bitset<200010>ans;
void update(int now,int l,int r,int ll,int rr,int e){
    if(l>rr||r<ll)return ;
    if(ll<=l&&rr>=r){
        tr[now].push_back(e);
        return ;
    }
    int mid=l+r>>1;
    update(now<<1,l,mid,ll,rr,e);
    update(now<<1|1,mid+1,r,ll,rr,e);
}
void getans(int now,int l,int r){
    stack<int>sta;
    for(auto x:tr[now]){
        if(bcj.find(edge[x].x)==bcj.find(edge[x].y)){
            for(int i=l;i<=r;i++) ans[i]=0;
            bcj.roll_back(sta);
            return ;
        } 
        bcj.merge(edge[x].x,edge[x].y+n,sta);
        bcj.merge(edge[x].x+n,edge[x].y,sta);
    }
    if(l!=r){
        int mid=l+r>>1;
        getans(now<<1,l,mid);
        getans(now<<1|1,mid+1,r);
    }
    bcj.roll_back(sta);
}
map<pair<int,int>,int>mp;
int cnte=0;
signed main(){
    ans.set();
    cin>>n>>m;
    bcj.init(n);
    for(int i=1;i<=m;i++){
        int x,y;
        cin>>x>>y;
        if(mp[{x,y}]){
            int from=mp[{x,y}];
            cnte++;
            edge[cnte].x=x,edge[cnte].y=y;
            update(1,1,m,from,i-1,cnte);
            mp[{x,y}]=0;
        }
        else mp[{x,y}]=i;
    }
    for(auto x:mp){
        if(x.second){
            cnte++;
            edge[cnte].x=x.first.first,edge[cnte].y=x.first.second;
            update(1,1,m,x.second,m,cnte);
        }
    }
    getans(1,1,m);
    for(int i=1;i<=m;i++) cout<<(ans[i]?"YES\n":"NO\n");
}

不太熟练所以线段树分治题单

AFO啦，留给大学的我

焚诀