




## 欧拉路

**欧拉路** 一口气经过所有的点和边，且所有的边只经过一次

**欧拉回路** 能形成回路的欧拉路

### 判定

#### 无向图

* 当且仅当无向图中所有点的度数均为偶数时才有欧拉回路
* 当且仅当无向图中有欧拉回路，或者有且仅有两个度数为奇数的点时才有欧拉路。对于后者，度数为奇数的点时起点或者终点
* 需注意图是否联通

#### 有向图

如果我们令一个点的出度记为 1，入度记为 -1，这个点所有的出度和入度相加，就是它的度数

* 当且仅当有向图中所有的点度数为 0 时才有欧拉回路
* 当且仅当有向图中有欧拉回路，或者有且仅有一个度数为 1 的点和一个度数为 -1 的点，其他所有的点度数均为 0。对于后者，度数为 1 的是起点，度数为 -1 的是终点
* 需注意图是否联通

### 打印方案

#### 递归遍历

直接 dfs 整个图，注意所有的边只能走一次，然后**在回溯时**打印答案。有向图和无向图都一样

**例题** [UVA10054](https://vjudge.net/problem/UVA-10054) 无向图求欧拉回路，打印方案

```cpp
#include bits/stdc++.h 
#define int long long
#define ull unsigned long long
#define ls(k) (k)  1
#define rs(k) (k)  1|1
#define debug(x) cout  #x  "="  x  endl
using namespace std;
const int inf=0x3f3f3f3f3f3f3f3f;
const int mod=0;
typedef pair int,int  pii;
int d[55],g[55][55];
void dfs(int u){
    for(int v=1;v =50;v++){
        if(g[u][v]){
            g[u][v]--,g[v][u]--;
            dfs(v);
            cout  v  " "  u  endl; // 回溯的时候
        }
    }
}
inline void subtask(){
    int n;cin  n;
    while(n--){
        int u,v;cin  u  v;
        d[u]++,d[v]++;
        g[u][v]++,g[v][u]++;
    }
    for(int i=1;i =50;i++) if(d[i]%2) return cout  "some beads may be lost"  endl,void();
    for(int i=1;i =50;i++) if(d[i]) return dfs(i),void();
}
signed main(){
    ios::sync_with_stdio(false);
    int t;cin  t;
    for(int i=1;i =t;i++){
        cout  "Case #"  i  endl;
        subtask();
        memset(d,0,sizeof(d));
        memset(g,0,sizeof(g));
        cout  endl;
    }
    return 0;
}
```

#### 模拟栈

如果递归深度过大的话，有可能会爆栈。此时我们考虑模拟递归时的栈来解决。基本思想是先从一个点一直往下dfs，dfs不动了，就把最后一个数字计入答案，然后再从第二个数字开始一直往下dfs

**例题** [POJ1780](https://vjudge.net/problem/POJ-1780) 有向图求欧拉路，打印方案，按字典序

题目大概意思是给定 $n$ 然后让我们生成一个字符串，使得字符串从头开始每看 $n$ 个数都是互不相同的 $n$ 位数字，且覆盖所有的 $n$ 位数字（含前导 0）

我们考虑现在已经有 $n-1$ 位数字，然后填入下一位数字，此时就构成了一个 $n$ 位数字，但同时后面的 $n-1$ 位数字又变成了新的”状态“，等待填入下一位数字

因此我们可以把所有的 $n-1$ 位数字视为一个状态，通过连有向边，即填数，来转移到另一个状态。每个状态向外连边只能经过一次，且需要把所有的边都走一遍，于是就转化为了欧拉路问题

```cpp
#include iostream 
#include algorithm 
#include stack 
using namespace std;
#include  cassert 

int nxt[1000006],n,cnt;
stack int  s,ans;
void dfs(int x){// 一直走下去
	while(nxt[x] 10){
		int to=(x*10+nxt[x])%cnt;
		s.push(to);
		nxt[x]++;
		x=to;
	}
}

int main(){
	ios::sync_with_stdio(false);
	while(cin  n    n){
		if(!n) break;
		if(n==1){
			cout  "0123456789"  endl;
			continue;
		}
		cnt=1;
		for(int i=1;i =n-1;i++) cnt*=10;
		for(int i=0;i cnt;i++) nxt[i]=0;
		for(int i=1;i =n-1;i++) cout  0;
		dfs(0);
		while(!s.empty()){// 走不动了，说明该回溯到上一个点，然后再向另一个方向一直走
			ans.push(s.top()%10);s.pop();
			if(!s.empty()) dfs(s.top());
		}
		int tot=n-1;
		while(!ans.empty()) cout  ans.top(),ans.pop(),tot++;
		cout  endl;
	}
	return 0;
}
```

#### 按字典序

先把点连出的所有边按照字典序排序，然后再求欧拉路，此时得到的方案其实就是按字典序的。但是由于我们是在回溯时记录答案，所以得到的方案其实是反的。所以我们还需要再把回溯时的要记录的点先放到一个栈里，然后最后再从栈中取出（相当于又反了一遍）

**例题** [P7771](https://www.luogu.com.cn/problem/P7771) 有向图求欧拉路板子题，按字典序输出方案

```cpp
#include bits/stdc++.h 
#define _ 200005
using namespace std;

inline int read(){
	int res=0,ch=getchar(),f=1;
	while(!isdigit(ch) and ch!=EOF){
		if(ch=='-') f=-1;
		ch=getchar();
	} 
	while(isdigit(ch)){
		res=(res  3)+(res  1)+(ch-'0');
		ch=getchar();
	}
	return res*f;
}

vector int  ve[_];
int bl[_],n,m,in[_],out[_];
stack int  st;
void dfs(int x){
	for(int i=bl[x];i ve[x].size();i=bl[x]){
		bl[x]++;
		dfs(ve[x][i]);
	}
	st.push(x);
}

int main(){
	n=read(),m=read();
	for(int i=1;i =m;i++){
		int u=read(),v=read();
		in[v]++,out[u]++;
		ve[u].push_back(v);
	}
	for(int i=1;i =n;i++) sort(ve[i].begin(),ve[i].end());
	int flag=0,cnt1=0,cnt2=0,s=0;
	for(int i=1;i =n;i++){
		if(in[i]!=out[i]) flag=true;
		if(in[i]-out[i]==1) cnt1++;
		if(out[i]-in[i]==1) s=i,cnt2++;
	}
	if(flag  !(cnt1==cnt2  cnt1==1)) return cout  "No",0;
	if(flag) dfs(s);
	else dfs(1);
	while(!st.empty()) cout  st.top()  ' ',st.pop();
	return 0;
}
```

## 网络流

### 最大流

弧优化的dinic算法

```cpp
int dis[_],rad[_],s,t;
bool bfs(){
	memset(dis,0,sizeof(dis));dis[s]=1;
	queue int  q;q.push(s);
	while(!q.empty()){
		int now=q.front();q.pop();
		rad[now]=head[now];
		for(int i=head[now];i;i=edge[i].nxt){
			int to=edge[i].to;
			if(!dis[to]  edge[i].w) dis[to]=dis[now]+1,q.push(to);
		}
	}
	return dis[t]!=0;
}
int dfs(int now,int rem){
	if(now==t) return rem;
	int tmp=rem;
	for(int i=rad[now];i;i=edge[i].nxt){
		int to=edge[i].to;rad[now]=i;
		if(dis[to]==dis[now]+1  edge[i].w){
			int k=min(edge[i].w,tmp);
			int d=dfs(to,k);
			edge[i].w-=d,edge[i^1].w+=d;
			tmp-=d;
			if(!tmp) break;
		}
	}
	return rem-tmp;
}
```

### DAG最小路径覆盖

#### 不相交路径

![image-20250306174049255](C:\Users\Caiwen\AppData\Roaming\Typora\typora-user-images\image-20250306174049255.png)

如图所示，一种不相交的最小路径覆盖为 1- 3- 4、2、5

一个点也可以视为一个长度为 $0$ 的路径

我们可以先建立一个二分图，左边是 $1\sim n$ ，右边也是 $1\sim n$。如果 DAG 上存在一个有向边 $(u,v)$ 的话，那么就把二分图中左边的 $u$ 和右边的 $v$ 连边。最后有
$$
\text{最小不相交路径覆盖}=\text{总点数}-\text{最大匹配}
$$
 可以理解为，我先让每个点被自己覆盖。然后如果我在二分图上建立了一个匹配了，那么就相当于延长了一个路径，也就是少花费了一个点

#### 可相交路径

还是如上图，一种可相交的最小路径覆盖为 1- 3- 4、2- 3- 5

我们先用 floyd 在图上搞传递闭包，然后如果 $u$ 能到达 $v$ ，就在把二分图左边的 $u$ 与右边的 $v$ 连边。最后答案还是按上式计算

可以理解为如果 $u$ 能到达 $v$ ，那么我们直接给连过去，先把中间的点省略，因为中间的点可能会被其他路径使用。如果后面的路径没使用到这个中间点的话，那么根据最大匹配的算法，一定会调整为选择使用中间的点，因为这样才能得到最大匹配

### 题目

#### P2472 [SCOI2007] 蜥蜴

https://www.luogu.com.cn/problem/P2472

**题目描述**

在一个 $r$ 行 $c$ 列的网格地图中有一些高度不同的石柱，第 $i$ 行 $j$ 列的石柱高度为 $h_{i,j}$。

一些石柱上站着一些蜥蜴，你的任务是让尽量多的蜥蜴逃到边界外。

每行每列中相邻石柱的距离为 $1$，蜥蜴的跳跃距离是 $d$，即蜥蜴可以跳到**平面距离**不超过 $d$ 的任何一个石柱上。

石柱都不稳定，每次当蜥蜴跳跃时，所离开的石柱高度减 $1$（如果仍然落在地图内部，则到达的石柱高度不变）。

如果该石柱原来高度为 $1$，则蜥蜴离开后消失，以后其他蜥蜴不能落脚。

任何时刻不能有两只蜥蜴在同一个石柱上。

**数据范围**

对于 $100\%$ 的数据满足：$1\le r,c\le20$，$1\le d\le 4$，$1\le h\le 3$。

**笔记**

题目总体来说有两个限制，一个是跳完之后高度就减一，减到 0 后就不能再跳到该位置了。另一个是同一时间只能有一个蜥蜴在一个柱子上

对于后者，其实可以忽略。如果我们能够得到一个蜥蜴的跳出方案，而这个蜥蜴要跳到的柱子已经被占用了，那么我们可以一直等待柱子解除占用，毕竟题目又没要求时间

于是就只需要考虑前面这个限制了。其实就是限制经过一个点的次数。对于这种要求，我们有如下建模方案：将点拆成入点和出点，然后入点到出点设置流量为限制次数的边

![image-20250306155451629](C:\Users\Caiwen\AppData\Roaming\Typora\typora-user-images\image-20250306155451629.png)

```cpp
#include bits/stdc++.h 
#define int long long
#define ull unsigned long long
#define ls(k) (k)  1
#define rs(k) (k)  1|1
#define debug(x) cout  #x  "="  x  endl
using namespace std;
const int inf=0x3f3f3f3f3f3f3f3f;
const int mod=0;
typedef pair int,int  pii;
int n,m,d,g[22][22],s,t,has[22][22],siz=1,head[900],dis[900],rad[900];
inline int get(int x,int y,int t){
    int res=(x-1)*m+y;
    return t==0? res:n*m+res;
}
inline int dis2(int x1,int y1,int x2,int y2){return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);}
struct Edge{int to,nxt,w;} edge[320004];
inline void _add(int u,int v,int w){edge[++siz].nxt=head[u],edge[siz].to=v,edge[siz].w=w,head[u]=siz;}
inline void add(int u,int v,int w){_add(u,v,w),_add(v,u,0);}
bool bfs(){
	memset(dis,0,sizeof(dis));dis[s]=1;
	queue int  q;q.push(s);
	while(!q.empty()){
		int now=q.front();q.pop();
		rad[now]=head[now];
		for(int i=head[now];i;i=edge[i].nxt){
			int to=edge[i].to;
			if(!dis[to]  edge[i].w) dis[to]=dis[now]+1,q.push(to);
		}
	}
	return dis[t]!=0;
}
int dfs(int now,int rem){
	if(now==t) return rem;
	int tmp=rem;
	for(int i=rad[now];i;i=edge[i].nxt){
		int to=edge[i].to;rad[now]=i;
		if(dis[to]==dis[now]+1  edge[i].w){
			int k=min(edge[i].w,tmp);
			int d=dfs(to,k);
			edge[i].w-=d,edge[i^1].w+=d;
			tmp-=d;
			if(!tmp) break;
		}
	}
	return rem-tmp;
}
inline void subtask(){
    cin  n  m  d;
    int cnt=0;
    s=0,t=2*n*m+1;
    for(int i=1;i =n;i++){
        string str;cin  str;
        for(int j=1;j =m;j++) g[i][j]=str[j-1]-'0';
    }
    for(int i=1;i =n;i++){
        string str;cin  str;
        for(int j=1;j =m;j++) has[i][j]=str[j-1]=='.'?0:1;
    }
    for(int i=1;i =n;i++){
        for(int j=1;j =m;j++){
            if(!g[i][j]) continue;
            if(has[i][j]) add(s,get(i,j,0),1),cnt++;
            add(get(i,j,0),get(i,j,1),g[i][j]);
            if(min(i,min(j,min(n-i+1,m-j+1))) =d) add(get(i,j,1),t,inf);
            for(int k=max(1ll,i-d);k =min(i+d,n);k++){
                for(int l=max(1ll,j-d);l =min(j+d,m);l++){
                    if(k==i  l==j) continue;
                    if(!g[k][l]) continue;
                    if(dis2(i,j,k,l) =d*d) add(get(i,j,1),get(k,l,0),inf);
                }
            }
        }
    }
    int ans=0;
    while(bfs()) ans+=dfs(s,inf);
    cout  cnt-ans;
}
signed main(){
    ios::sync_with_stdio(false);
    int t=1;//cin  t;
    while(t--) subtask();
    return 0;
}
```

#### P2754 [CTSC1999] 家园 / 星际转移问题

https://www.luogu.com.cn/problem/P2754

**题目描述**

有 地球，月球，还有额外的 $n$ 个星球，然后有 $m$ 个宇宙飞船，可以分别以自己的某个顺序循环在几个星球之间穿梭，每次穿梭消耗一个单位的时间。每个飞船都有自己的容量限制

现在问至少需要多少时间才能把 $k$ 个人从 地球 运往 月球

**数据范围**

- $1 \leq n \leq 13$。
- $1 \leq m \leq 20$。
- $1 \leq k \leq 50$。
- $1 \leq r_i \leq n + 2$。
- $-1 \leq S_{i, j}\leq n$。

**笔记**

先用并查集判断是否有解

然后题目中这个”时间“有点不好搞。这里又引出一个建模方法：根据时间分层，具体如图：

![image-20250306160443125](C:\Users\Caiwen\AppData\Roaming\Typora\typora-user-images\image-20250306160443125.png)

然后我们枚举时间，建图跑最大流，直到得到的流量等于 $k$ 即可得到答案

注意理论上这种问题应该是二分答案的，但我们考虑直接枚举，因为如果有解，那么最大耗时不会超过 $kn^2$ ，所以枚举可以。而且当我们枚举完一个答案再往下枚举的时候，我们可以直接在现有的图上补充点和边，而不用再重新建立一个完整的图，这是二分做不到的。而且我们跑完最大流后，补充点和边，直接再基于上一次的残留网络继续跑最大流就可以了。所以直接枚举的效率并不会太低

```cpp
#include bits/stdc++.h 
#define ull unsigned long long
#define ls(k) (k)  1
#define rs(k) (k)  1|1
#define debug(x) cout  #x  "="  x  endl
using namespace std;
const int inf=0x3f3f3f3f3f3f3f3f;
const int mod=0;
typedef pair int,int  pii;
#define _ 1000006
struct Edge{int nxt,to,w;} edge[_  1];
int head[_],siz=1,opa[_],fa[_],las[_];
inline int find(int x){while(x!=fa[x]) x=fa[x]=fa[fa[x]];return x;}
inline void _add(int u,int v,int w){edge[++siz].nxt=head[u],edge[siz].to=v,edge[siz].w=w,head[u]=siz;}
inline void add(int u,int v,int w){_add(u,v,w),_add(v,u,0);} 
int dis[200005],rad[_],s,t;
bool bfs(){
	memset(dis,0,sizeof(dis));dis[s]=1;
	queue int  q;q.push(s);
	while(!q.empty()){
		int now=q.front();q.pop();
		rad[now]=head[now];
		for(int i=head[now];i;i=edge[i].nxt){
			int to=edge[i].to;
			if(!dis[to]  edge[i].w) dis[to]=dis[now]+1,q.push(to);
		}
	}
	return dis[t]!=0;
}
int dfs(int now,int rem){
	if(now==t) return rem;
	int tmp=rem;
	for(int i=rad[now];i;i=edge[i].nxt){
		int to=edge[i].to;rad[now]=i;
		if(dis[to]==dis[now]+1  edge[i].w){
			int k=min(edge[i].w,tmp);
			int d=dfs(to,k);
			edge[i].w-=d,edge[i^1].w+=d;
			tmp-=d;
			if(!tmp) break;
		}
	}
	return rem-tmp;
}
vector int  to[_];
inline void subtask(){
    int n,m,k;cin  n  m  k;
    for(int i=0;i =n+1;i++) fa[i]=i;
    for(int i=1;i =m;i++){
        cin  opa[i];
        int r;cin  r;
        for(int j=1,x;j =r;j++){
            cin  x;
            if(x==-1) x=1;
            else if(x!=0) x+=1;
            to[i].push_back(x);
        }
        for(int j=0;j to[i].size();j++){
            int u=to[i][j],v=to[i][(j+1)%to[i].size()];
            u=find(u),v=find(v);
            if(u!=v) fa[u]=v;
        }
    }
    if(find(1)!=find(0)) return cout  0,void();
    s=0;
    for(int i=0;i =n+1;i++) las[i]=i+1;
    int ans=0,base=n+3;
    add(s,las[0],k);
    int ok=0;
    while(true){
        ans++;
        for(int i=0;i =n+1;i++) add(las[i],base+i,inf);
        for(int i=1;i =m;i++){
            int u=to[i][(ans-1)%to[i].size()];
            int v=to[i][ans%to[i].size()];
            add(las[u],base+v,opa[i]);
        }
        for(int i=0;i =n+1;i++) las[i]=base+i;
        t=base+1;
        base=base+n+1+1;
        while(bfs()) ok+=dfs(s,inf);
        if(ok==k) return cout  ans  endl,void();
    }
}
signed main(){
    ios::sync_with_stdio(false);
    int t=1;//cin  t;
    while(t--) subtask();
    return 0;
}
```

#### P2765 魔术球问题

https://www.luogu.com.cn/problem/P2765

**题目描述**

假设有 $n$ 根柱子，现要按下述规则在这 $n$ 根柱子中依次放入编号为 $1$，$2$，$3$，...的球“

1. 每次只能在某根柱子的最上面放球。

2. 同一根柱子中，任何 $2$ 个相邻球的编号之和为完全平方数。

试设计一个算法，计算出在 $n$ 根柱子上最多能放多少个球。例如，在 $4$ 根柱子上最多可放 $11$ 个球。

对于给定的 $n$，计算在 $n$ 根柱子上最多能放多少个球。

**数据范围**

对于 $100\%$ 的数据，保证 $1 \leq n \leq 55$。

**笔记**

如果两个数能构成完全平方数，那么我们就把这两个数字连边，并规定一定是大的数字连向小的数字（其实小的数字往大的数字连边也可以，总之就是要保证一个顺序，但是大连小的话在后面补充建边时更有优势）

如果我们要判断答案是否为 $x$，那么就相当于现在我们有一个含有 $x$ 个点的 DAG，并去判断这个 DAG 的最小不相交路径覆盖是否为 $n$

我们沿用上道题的做法，枚举答案。考虑答案增加一，那么我们就相当于二分图两边多了个点，然后把这个点连向相加可以为完全平方数的数，然后在仅对新增的这个点跑最大匹配就可以了

设当前点数为 $ans$，当前最大匹配为 $ok$，那么如果 $ans-ok=n$ 说明 $ans$ 即为答案。$ans$ 增加 $1$，$ok$ 可能增加 $1$ 也可能不增加，所以 $ans-ok$ 是单调不减的，所以直接枚举的正确性是可以保证的

```cpp
#include bits/stdc++.h 
#define int long long
#define ull unsigned long long
#define ls(k) (k)  1
#define rs(k) (k)  1|1
#define debug(x) cout  #x  "="  x  endl
using namespace std;
const int inf=0x3f3f3f3f3f3f3f3f;
const int mod=0;
typedef pair int,int  pii;
vector int  ve[1000006];
int match[1000006],t[1000006],nxt[1000006];
bool dfs(int x,int tag){
    if(t[x]==tag) return false;
    t[x]=tag;
    for(int to:ve[x]) if(!match[to]||dfs(match[to],tag)) return match[to]=x,true;
    return false;
}
inline void subtask(){
    int n;cin  n;
    int ans=0,ok=0,tag=0;
    while(true){
        ans++;
        for(int i=2;i*i 2*ans;i++){
            if(i*i =ans) continue;
            ve[ans].push_back(i*i-ans);
        }
        if(dfs(ans,++tag)) ok++;
        if(ans-ok n) break;
    }
    ans--;
    cout  ans  endl;
    for(int i=1;i =ans;i++) nxt[match[i]]=i;
    for(int i=1;i =ans;i++){
        if(match[i]) continue;
        int now=i;cout  now  ' ';
        while(nxt[now]) cout  nxt[now]  ' ',now=nxt[now];
        cout  endl;
    }
}
signed main(){
    ios::sync_with_stdio(false);
    int t=1;//cin  t;
    while(t--) subtask();
    return 0;
}
```

#### P2766 最长不下降子序列问题

https://www.luogu.com.cn/problem/P2766

**题目描述**

给定正整数序列 $x_1 \ldots, x_n$。

1. 计算其最长不下降子序列的长度 $s$。
2. 如果每个元素只允许使用一次，计算从给定的序列中最多可取出多少个长度为 $s$ 的不下降子序列。
3. 如果允许在取出的序列中多次使用 $x_1$ 和 $x_n$（其他元素仍然只允许使用一次），则从给定序列中最多可取出多少个**不同的**长度为 $s$ 的不下降子序列。

令 $a_1, a_2, \ldots, a_s$ 为构造 $S$ 时所使用的下标，$b_1, b_2, \ldots, b_s$ 为构造 $T$ 时所使用的下标。且 $\forall i \in [1,s-1]$，都有 $a_i \lt a_{i+1}$，$b_i \lt b_{i+1}$。则 $S$ 和 $T$ **不同**，当且仅当 $\exists i \in [1,s]$，使得 $a_i \neq b_i$。

**数据范围**

$1 \le n\le 500$

**笔记**

直接使用 dp 跑最长不下降子序列。不用 $O(n\log n)$ 做法的原因是 dp 的话我们就知道以每个数结尾能够形成的最长不下降子序列的长度是多少，这有助于我们计算方案

如果所有的数都可以重复取，那么我们可以用组合数学直接计算出来方案个数。但现在一个数只能取一次，即使考虑 dp 计算的话，后效性也太大

于是此时网络流又派上用场了，我们按 dp 转移阶段分层，然后如果一个点能够转移到另一个点，就连边。直接这么连的话有些点会被取多次。于是又是套路的拆点，限制经过点的流量

对于第三问，把边权改为 inf 后继续增广就可以了

```cpp
#include bits/stdc++.h 
#define int long long
#define ull unsigned long long
#define ls(k) (k)  1
#define rs(k) (k)  1|1
#define debug(x) cout  #x  "="  x  endl
using namespace std;
const int inf=0x3f3f3f3f3f3f3f3f;
const int mod=0;
typedef pair int,int  pii;
#define _ 505
int a[_],dp[_],siz=1,head[_],s,t;
struct Edge{int nxt,to,w;} edge[1000006];
inline void _add(int u,int v,int w){edge[++siz].nxt=head[u],edge[siz].to=v,edge[siz].w=w,head[u]=siz;}
inline void add(int u,int v,int w){_add(u,v,w),_add(v,u,0);}
int dis[_],rad[_];
bool bfs(){
	memset(dis,0,sizeof(dis));dis[s]=1;
	queue int  q;q.push(s);
	while(!q.empty()){
		int now=q.front();q.pop();
		rad[now]=head[now];
		for(int i=head[now];i;i=edge[i].nxt){
			int to=edge[i].to;
			if(!dis[to]  edge[i].w) dis[to]=dis[now]+1,q.push(to);
		}
	}
	return dis[t]!=0;
}
int dfs(int now,int rem){
	if(now==t) return rem;
	int tmp=rem;
	for(int i=rad[now];i;i=edge[i].nxt){
		int to=edge[i].to;rad[now]=i;
		if(dis[to]==dis[now]+1  edge[i].w){
			int k=min(edge[i].w,tmp);
			int d=dfs(to,k);
			edge[i].w-=d,edge[i^1].w+=d;
			tmp-=d;
			if(!tmp) break;
		}
	}
	return rem-tmp;
}
inline void subtask(){
    int n;cin  n;
    for(int i=1;i =n;i++) cin  a[i];
    for(int i=1;i =n;i++) dp[i]=1;
    int maxx=1;
    for(int i=2;i =n;i++) for(int j=1;j i;j++) if(a[j] =a[i]) dp[i]=max(dp[i],dp[j]+1),maxx=max(maxx,dp[i]);
    cout  maxx  endl;
    if(maxx==1) return cout  n  endl  n,void();
    s=0,t=2*n+1;
    int e1,en;
    for(int i=1;i =n;i++){
        add(2*i-1,2*i,1);
        if(i==1) e1=siz-1;
        if(i==n) en=siz-1;
        if(dp[i]==1) add(s,2*i-1,inf);
        if(dp[i]==maxx) add(2*i,t,inf);
        for(int j=1;j i;j++){
            if(!(a[j] =a[i]  dp[j]==dp[i]-1)) continue;
            add(2*j,2*i-1,1);
        }
    }
    int ans=0;
    while(bfs()) ans+=dfs(s,inf);
    cout  ans  endl;
    edge[e1].w=inf;
    edge[en].w=inf;
    while(bfs()) ans+=dfs(s,inf);
    cout  ans;
}
signed main(){
    ios::sync_with_stdio(false);
    int t=1;//cin  t;
    while(t--) subtask();
    return 0;
}
```







## 题目

### P4008 [NOI2003] 文本编辑器

https://www.luogu.com.cn/problem/P4008

**题目描述**

实现一个文本编辑器，有如下操作：

1. 将光标移动到某个位置
2. 在光标后插入一个字符串
3. 删除光标后若干字符
4. 获取光标后若干字符
5. 光标向前移动
6. 光标向后移动

**笔记**

```cpp
#include bits/stdc++.h 
#define int long long
#define ull unsigned long long
#define ls(k) (k)  1
#define rs(k) (k)  1|1
#define il inline
#define debug(x) cout  #x  "="  x  endl
using namespace std;
const int inf=0x3f3f3f3f3f3f3f3f;
const int mod=0;
typedef pair int,int  pii;
#define _ 1024*1024*2
struct FHQ{
    int tot=0;
    struct Node{int ls,rs,dat,siz;char val;} tree[_];
    #define nt tree[k]
    #define lt tree[tree[k].ls]
    #define rt tree[tree[k].rs]
    il void update(int k){nt.siz=1+lt.siz+rt.siz;}
    il int create(char v){int k=++tot;nt.dat=rand(),nt.val=v,nt.siz=1;return tot;}
    il int merge(int x,int y){
        if(!x||!y) return x+y;
        if(tree[x].dat tree[y].dat) return tree[x].rs=merge(tree[x].rs,y),update(x),x;
        else return tree[y].ls=merge(x,tree[y].ls),update(y),y;
    }
    void split(int k,int x,int  l,int  r){
        if(!k) return l=r=0,void();
        if(lt.siz+1 =x) l=k,split(nt.rs,x-lt.siz-1,nt.rs,r);
        else r=k,split(nt.ls,x,l,nt.ls);
        update(k);
    }
    void print(int k){// 中序遍历打印
        if(k==0) return;
        print(nt.ls);cout  nt.val;print(nt.rs);
    }
} tree;
inline void subtask(){
    srand(time(NULL));
    int pos=0,root=0,n,l,r;cin  n;
    while(n--){
        char op[7];cin  op;
        if(op[0]=='M') cin  pos;
        if(op[0]=='I'){
            int len;cin  len;
            tree.split(root,pos,l,r);
            for(int i=1;i =len;i++){
                char ch=getchar();
                while(ch 32||ch 126) ch=getchar();
                l=tree.merge(l,tree.create(ch));
            }
            root=tree.merge(l,r);
        }
        if(op[0]=='D'){
            int len,tmp;cin  len;
            tree.split(root,pos+len,l,r);tree.split(l,pos,l,tmp);
            root=tree.merge(l,r);
        }
        if(op[0]=='G'){
            int len,tmp;cin  len;
            tree.split(root,pos+len,l,r);tree.split(l,pos,l,tmp);
            tree.print(tmp);cout  endl;
            root=tree.merge(tree.merge(l,tmp),r);
        }
        if(op[0]=='P') pos--;
        if(op[0]=='N') pos++;
    }
}
signed main(){
    int t=1;//cin  t;
    while(t--) subtask();
    return 0;
}
```

### P3391 【模板】文艺平衡树

https://www.luogu.com.cn/problem/P3391

**题目描述**

维护一个序列，有若干区间翻转操作，输出所有操作后，得到的序列

**笔记**

对区间 $[l,r]$ 进行翻转，可以视为将区间 $[l,k]$ 和区间 $[k+1,r]$ 交换，然后这两个区间再分别递归进行这个操作

也可以视为找到一个轴 $k(l k r)$ ，将区间 $[l,k-1]$ 和 $[k+1,r]$ 交换，然后这两个区间再分别递归进行这个操作

然后对于本题我们在 fhq treap 上引入懒标记，每次分裂或者合并时 pushdown 这个懒标记

```cpp
#include iostream 
#define maxn 100005
using namespace std;

int id,val[maxn],dat[maxn],size[maxn],ch[maxn][2],root,tag[maxn];
inline int create(int x){
	id++;
	val[id]=x;
	dat[id]=rand();
	size[id]=1;
	return id;
}
inline void pushup(int k){
	size[k]=size[ch[k][0]]+1+size[ch[k][1]];
}
inline void pushdown(int k){
	if(tag[k]){
		tag[ch[k][0]]^=1;
		tag[ch[k][1]]^=1;
		swap(ch[k][0],ch[k][1]);
		tag[k]=0;
	}
}
void split(int now,int k,int  x,int  y){
	if(!now) x=y=0;
	else{
		pushdown(now);
		int u=size[ch[now][0]]+1;
		if(u =k){
			x=now;
			split(ch[now][1],k-u,ch[now][1],y);
			pushup(x);
		}else{
			y=now;
			split(ch[now][0],k,x,ch[now][0]);
			pushup(y);
		}
	}
}
int merge(int x,int y){
	if(!x||!y) return x+y;
	pushdown(x);
	pushdown(y);
	if(dat[x] =dat[y]){
		ch[x][1]=merge(ch[x][1],y);
		pushup(x);
		return x;
	}else{
		ch[y][0]=merge(x,ch[y][0]);
		pushup(y);
		return y;
	}
}
void reverse(int l,int r){
	int p1=0,p2=0,p3=0,p4=0;
	split(root,l-1,p1,p2);
	split(p2,(r-l+1),p3,p4);
	tag[p3]^=1;
	p2=merge(p3,p4);
	root=merge(p1,p2);
}
void print(int k){
	pushdown(k);
	if(ch[k][0]) print(ch[k][0]);
	cout  val[k]  " ";
	if(ch[k][1]) print(ch[k][1]);
}

int main(){
	int n,m;
	cin  n  m;
	int l,r;
	for(int i=1;i =n;i++){
		//int k;
		//cin  k;
		split(root,i-1,l,r);
		root=merge(merge(l,create(i)),r);
	}
	while(m--){
		cin  l  r;
		reverse(l,r);
	}
	print(root);
	return 0;
}
```

### P5055 【模板】可持久化文艺平衡树

https://www.luogu.com.cn/problem/P5055

**题目描述**

每次操作创建一个新版本。然后有如下的操作，可以基于之前的版本进行修改：

1. 在某个位置插入一个数
2. 删除某个位置上的数字
3. 翻转区间
4. 查询区间和

**笔记**

考虑创建新版本时，很多节点是和上一个版本是重合的，所以我们对于重合的点，直接重用，只产生新的发生改变的点。每次 pushdown 和 split 的时候克隆

至于节点数组开多大，直接估计比较麻烦，我们可以直接根据题目的空间的限制尽可能开大

```cpp
#include bits/stdc++.h 
#define int long long
#define ull unsigned long long
#define ls(k) (k)  1
#define rs(k) (k)  1|1
#define debug(x) cout  #x  "="  x  endl
using namespace std;
const int inf=0x3f3f3f3f3f3f3f3f;
const int mod=0;
typedef pair int,int  pii;
#define _ 200005
struct FHQ{
    struct Node{int ls,rs,val,dat,siz,lazy,sum;} tree[_  6];
    int tot=0;
    #define nt tree[k]
    #define lt tree[tree[k].ls]
    #define rt tree[tree[k].rs]
    inline int create(int v){int k=++tot;nt.dat=rand(),nt.siz=1,nt.sum=v,nt.val=v;return tot;}
    inline int clone(int k){tree[++tot]=nt;return tot;}
    inline void update(int k){nt.siz=1+lt.siz+rt.siz,nt.sum=lt.sum+rt.sum+nt.val;}
    void pushdown(int k){
        if(!nt.lazy) return;
        if(nt.ls) nt.ls=clone(nt.ls);
        if(nt.rs) nt.rs=clone(nt.rs);
        swap(nt.ls,nt.rs);
        lt.lazy^=1,rt.lazy^=1;
        nt.lazy=0;
    }
    void split(int k,int x,int  l,int  r){
        if(!k) return l=r=0,void();
        pushdown(k);
        if(lt.siz+1 =x) l=clone(k),split(tree[l].rs,x-lt.siz-1,tree[l].rs,r),update(l);
        else r=clone(k),split(tree[r].ls,x,l,tree[r].ls),update(r);
    }
    int merge(int l,int r){
        if(l==0||r==0) return l+r;
        pushdown(l);pushdown(r);
        if(tree[l].dat tree[r].dat) return tree[l].rs=merge(tree[l].rs,r),update(l),l;
        else return tree[r].ls=merge(l,tree[r].ls),update(r),r;
    }
} tree;
int root[_];
inline void subtask(){
    srand(time(NULL));
    int now=0,l,r,tmp,lastans=0,n;cin  n;
    while(n--){
        int v,op;cin  v  op;
        if(op==1){
            int p,x;cin  p  x;p^=lastans,x^=lastans;
            tree.split(root[v],p,l,r);
            root[++now]=tree.merge(tree.merge(l,tree.create(x)),r);
        }
        if(op==2){
            int p;cin  p;p^=lastans;
            tree.split(root[v],p,tmp,r);
            tree.split(tmp,p-1,l,tmp);
            root[++now]=tree.merge(l,r);
        }
        if(op==3){
            int x,y;cin  x  y;x^=lastans,y^=lastans;
            tree.split(root[v],y,l,r);
            tree.split(l,x-1,l,tmp);
            tree.tree[tmp].lazy^=1;
            root[++now]=tree.merge(tree.merge(l,tmp),r);
        }
        if(op==4){
            int x,y;cin  x  y;x^=lastans,y^=lastans;
            tree.split(root[v],y,l,r);
            tree.split(l,x-1,l,tmp);
            lastans=tree.tree[tmp].sum;
            cout  lastans  endl;
            root[++now]=tree.merge(tree.merge(l,tmp),r);
        }
    }
}
signed main(){
    ios::sync_with_stdio(false);
    int t=1;//cin  t;
    while(t--) subtask();
    return 0;
}
```







## 拉格朗日插值

### 朴素做法

$n+1$ 个点可以确定一个 $n$ 次多项式。拉格朗日插值可以实现，对于某个 $n$ 次多项式函数 $f(x)$ ，如果我们已知了这 $n+1$ 个点，就可以 $O(n^2)$ 的时间复杂度求出 $f(k)$

具体来说，我们我们知道了多项式函数上的 $n+1$ 个点 $(x_i,y_i)$，然后有公式：
$$
f(k)=\sum_{i=1}^{n+1} y_i \prod_{j\neq i} \frac{k-x_j}{x_i-x_j}
$$

### 点为连续情况

如果 $x_i$ 是连续的，比如 $x_1=1,x_2=2,...,x_i=i$，那么我们可以通过预处理，$O(n)$ 的时间复杂度求出 $f(k)$

首先预处理出阶乘 $fac_i$ 以及阶乘逆元，然后对于要求出的点 $k$，预处理出下面两值：
$$
pre_i=\prod_{j=1}^i k-j
$$

$$
suf_i=\prod_{j=i}^{n+1}k-j
$$

然后有公式：
$$
f(k)=\sum_{i=1}^{n+1}y_i\frac{pre_{i-1}\times suf_{i+1}}{fac_{i-1}\times fac_{n+1-i}\times (-1)^{n+1-i}}
$$

### 题目

#### F. The Sum of the k-th Powers

https://codeforces.com/problemset/problem/622/F

**题目描述**

求 $(\sum_{i=1}^ni^k)\pmod{10^9+7}$

**数据范围**

$1\le n \le 10^9$，$0\le k \le 10^6$

**笔记**

$k$ 次方求和，求和公式是 $k+1$ 次的，我们先暴力算出 $k+2$ 个点，然后插值即可

```cpp
#include bits/stdc++.h 
#define int long long
#define ull unsigned long long
#define ls(k) (k)  1
#define rs(k) (k)  1|1
#define debug(x) cout  #x  "="  x  endl
using namespace std;
const int inf=0x3f3f3f3f3f3f3f3f;
const int mod=1e9+7;
typedef pair int,int  pii;
#define _ 2000006
int fac[_],inv[_],pre[_],suf[_],y[_];
inline int qpow(int a,int p,int res=1){for(;p;p  =1,a=a*a%mod)if(p 1)res=res*a%mod;return res;}
inline void subtask(){
    fac[0]=1;
    for(int i=1;i =2000000;i++) fac[i]=fac[i-1]*i%mod;
    int n,k;cin  n  k;
    for(int i=1;i =k+2;i++) y[i]=(y[i-1]+qpow(i,k))%mod;
    pre[0]=1;
    for(int i=1;i =k+2;i++) pre[i]=pre[i-1]*(n-i)%mod;
    suf[k+3]=1;
    for(int i=k+2;i =1;i--) suf[i]=suf[i+1]*(n-i)%mod;
    int ans=0;
    for(int i=1;i =k+2;i++) ans+=((k+2-i)%2==0?1:-1)*y[i]*pre[i-1]%mod*suf[i+1]%mod*qpow(fac[i-1],mod-2)%mod*qpow(fac[k+2-i],mod-2)%mod,ans%=mod;
    cout  (ans+mod)%mod;
}
signed main(){
    ios::sync_with_stdio(false);
    int t=1;//cin  t;
    while(t--) subtask();
    return 0;
}
```

#### P4593 [TJOI2018] 教科书般的亵渎

https://www.luogu.com.cn/problem/P4593

**题目描述**

现在有 $1\sim n$，共 $n$ 个数字，然后去掉其中 $m$ 个数字。然后每次操作，都可以让所有的数字减一，如果减完之后有数字变为 $0$，则去掉该数字，然后再把所有的数字减一，由数字归零引发的减一也算在这次操作中。我们设 $k$ 为需要多少次操作才能把所有的数字归零。每次操作，对于每个数字，都会产生 $x^k$ 的分数，其中 $x$ 为减一之前的数字。

求出把所有数字归零后，获得的总分数。多组测试数据

**数据范围**

- 对于 $10\%$ 的数据，有 $m=0$；
- 对于 $20\%$ 的数据，有 $m\leq1$；
- 对于 $30\%$ 的数据，有 $m\leq2$
- 对于 $40\%$ 的数据，有 $m\leq3$；
- 对于 $50\%$ 的数据，有 $m\leq4$；
- 对于 $60\%$ 的数据，有 $m\leq5$；
- 对于 $100\%$ 的数据，有 $m\leq50$，$n\leq10^{13}$，$1 \le a_i  n$。

**笔记**

首先需要看出 $k=m+1$，手推几个样例然后感性理解一下就能得出来了

去掉数字后，会把 $1\sim n$ 分成若干数字连续的段

然后我们把贡献拆开，对于一个数字，考虑他会对总分数产生什么样的贡献。设被去掉的数字为 $a_i$，然后设  令 $a_0=0$，我们发现数字 $x$ 对答案的贡献为 $\sum_{i=0}^m(x-a_i)^k$，其中只计算小于 $x$ 的 $a_i$。手推几个样例然后感性理解一下就能得出来了

我们又发现，如果 $a_i$ 固定，$x$ 在某个区间上连续变化的话，$x-a_i$ 也是连续变化的，$(x-a_i)^k$ 就可以像上道题那样求出

于是答案变为了 $\sum_{i=0}^m\sum_{x=l_j}^{r_j} (x-a_i)^k$

```cpp
#include bits/stdc++.h 
#define int long long
#define ull unsigned long long
#define ls(k) (k)  1
#define rs(k) (k)  1|1
#define debug(x) cout  #x  "="  x  endl
using namespace std;
const int inf=0x3f3f3f3f3f3f3f3f;
const int mod=1e9+7;
typedef pair int,int  pii;
int fac[66],inv[66],y[66],n,m,pre[66],suf[66];
inline int qpow(int a,int p,int res=1){for(;p;p  =1,a=a*a%mod)if(p 1)res=res*a%mod;return res;}
inline void subtask(){
    cin  n  m;
    vector int  ve;
    for(int i=1,x;i =m;i++) cin  x,ve.push_back(x);
    ve.push_back(0);sort(ve.begin(),ve.end());
    int end=n;
    for(int i=ve.size()-1;i =0;i--) if(ve[i]==end) m--,end--,n--;
    int k=m+1;
    for(int i=1;i =k+2;i++) y[i]=(y[i-1]+qpow(i,k))%mod;
    auto f=[k](int x){
        if(x==0) return (long long)0;
        pre[0]=1;
        for(int i=1;i =k+2;i++) pre[i]=pre[i-1]*(x-i)%mod;
        suf[k+3]=1;
        for(int i=k+2;i =1;i--) suf[i]=suf[i+1]*(x-i)%mod;
        int res=0;
        for(int i=1;i =k+2;i++) res+=((k+2-i)%2==0?1:-1)*y[i]*pre[i-1]%mod*suf[i+1]%mod*inv[i-1]%mod*inv[k+2-i]%mod,res%=mod;
        return (res+mod)%mod;
    };
    auto flr=[f](int l,int r){return (f(r)-f(l-1)+mod)%mod;};

    vector pii  ran;
    int l=1;
    for(auto x:ve){
        if(!x) continue;
        if(x==l) l++;
        else{
            ran.push_back(pii(l,x-1));
            l=x+1;
        }
    }
    if(l =n) ran.push_back(pii(l,n));
    int res=0;
    for(auto to:ran){
        for(auto x:ve){
            if(x to.first) break;
            res+=flr(to.first-x,to.second-x);res%=mod;
        }
    }
    cout  res  endl;
}
signed main(){
    fac[0]=1;
    for(int i=1;i =60;i++) fac[i]=fac[i-1]*i%mod;
    inv[60]=qpow(fac[60],mod-2);
    for(int i=60-1;i =0;i--) inv[i]=inv[i+1]*(i+1)%mod;
    ios::sync_with_stdio(false);
    int t;cin  t;
    while(t--) subtask();
    return 0;
}
```


