---
title: P6148 Swapity Swapity Swap S
type: 题解
tags:
  - 信息竞赛题解
  - 倍增
  - 快速幂
---

# P6148 [USACO20FEB] Swapity Swapity Swap S

Farmer John 的 $N$ 头奶牛（$1\leq N\leq 10^5$）站成一排。对于每一个 $1\leq i\leq N$，从左往右数第 $i$ 头奶牛的编号为 $i$。

Farmer John 想到了一个新的奶牛晨练方案。他给奶牛们 $M$ 对整数 $(L_1,R_1)\ldots (L_M,R_M)$，其中 $1\leq M\leq 100$。他让她们重复以下包含 $M$ 个步骤的过程 $K$（$1\leq K\leq 10^9$）次：

对于从 $1$ 到 $M$ 的每一个 $i$：
- 当前从左往右数在位置 $L_i\ldots R_i$ 的奶牛序列反转她们的顺序。
- 当奶牛们重复这一过程 $K$ 次后，请对每一个 $1\leq i\leq N$ 输出从左往右数第 $i$ 头奶牛的编号。

## 思路1:

首先看暴力，暴力 $O(nmk)$，非常的去世。

首先我们可以自然而然的想到用矩阵代表每一次变换（即代表一次$(L_i,R_i)$）的交换。

初始答案矩阵：
$$
\begin{bmatrix}
1\\

2\\

3\\
\vdots\\

n

\end{bmatrix}
$$
那么对于一次交换 $(L_i,R_i)$ 的转移，我们可以构造出转移矩阵：
$$
\begin{bmatrix}
1 & 0 & 0 & ... & 0 \\
0 & 1 & 0 & ... & 0 \\
0 & 0 & 1 & ... & 0\\
\vdots & \vdots & \vdots& ([L_i,R_i])& \vdots\\
0 & 0 & 0 & ... & 1
\end{bmatrix}
$$
其中 $[L_i,R_i]$ 的子矩阵是：
$$
\begin{bmatrix}
0 & 0 & ... & 0 & 1 \\
0 & 0 & ... & 1 & 0 \\
\vdots & \vdots & \ddots & \vdots & \vdots\\
0 & 1 & ... & 0 & 0\\
1 & 0 & ... & 0 & 0
\end{bmatrix}
$$
其中副斜对角线上的的值全为 $1$.

转移矩阵表示的是其他元素不变,$(L_i,R_i)$ 之间的元素全部交换.

那么我们只需要对 $m$ 个操作的矩阵全部乘起来,然后自乘 $k$ 次,最后在与答案矩阵相乘即可.

但是我们发现 $n \le 1e5$,也就是说我们的转移矩阵的大小要是 $1e5 \times 1e5$ 的大小,不 $TLE$ 也得 $MLE$.

我们发现,转移矩阵的每一行,每一列都只对应着一个 $1$.

则我们可以把这个矩阵压缩成 $1 \times 1e5$ 的矩阵:
$$
\begin{bmatrix}
1\\
2\\
3\\
\vdots\\
\overbrace{R_i}\\
R_i - 1\\
\vdots\\
L_i + 1\\
\underbrace{L_i}\\
R_i + 1\\
\vdots\\
n
\end{bmatrix}
$$
第 $i$ 行的元素代表了原转移矩阵第 $i$ 行中的 $1$ 在第几列.

那么我们转移矩阵的相乘就可以变成: (其中 $ans$ 是答案矩阵,$a,b$ 是转移矩阵.)
$$
a \times b:\\
ans_i = b_{a_i}
$$
矩阵的自乘就会变为:
$$
a^2 :\\
ans_i = a_{a_i}
$$
这样看就很简单了,我们定义 `MATRIX` 结构体,在里面重载运算符实现 $'\times'$ 运算即可.

$code:$

```cpp
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN = 1e5 + 7;
const int MAXM = 105;
int n,m,k;
struct OPERATE{
	int l,r;
}op[MAXM];
struct MATRIX{
	int a[MAXN];
	void init(){ for(int i = 1;i <= n;i++) a[i] = i; }
	MATRIX operator*(const MATRIX &other){
		MATRIX ans;
		int res[MAXN];
		for(int i = 1;i <= n;i++) res[i] = other.a[i];
		for(int i = 1;i <= n;i++) ans.a[i] = res[a[i]];
		return ans;
	}
	void print_ans(){ for(int i = 1;i <= n;i++) cout << a[i] << endl; }
}op_matrix[MAXM];
MATRIX anss;
MATRIX qpow(MATRIX a,int x){
	MATRIX res;
	res.init();
	while(x){
		if(x & 1) res = a * res;
		a = a * a;
		x >>= 1;
	}	
	return res;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m >> k;
	for(int i = 1;i <= m;i++){
		cin >> op[i].l >> op[i].r;
		for(int j = op[i].l;j <= op[i].r;j++) op_matrix[i].a[op[i].r - (j - op[i].l)] = j;
		for(int j = 1;j <= n;j++) if(op_matrix[i].a[j] == 0) op_matrix[i].a[j] = j;
	}
	anss.init();
	for(int i = 1;i <= m;i++) anss = op_matrix[i] * anss;
	anss = qpow(anss,k);
	anss.print_ans();
	return 0;
}
```

## 思路2

我们发现,对于一次反转后,每个位置上对应的数是独一无二的.

我们发现这跟函数的定义很像,即定义域上的每一个值都对应了唯一的一个值.

对于每 $i$ 次操作,我们设为 $f_i$ 为一次映射,则对于一次操作序列的映射效果 $g$,我们有:
$$
g(E) = f_1(f_2(...f_m(E)))
$$
其中 $E$ 表示初始状态.

我们用 $[1,2,...,(R_i,R_i - 1,...,L_i),R_i + 1,...,n]$ 来表示一次操作序列中的一次操作,那么我们只需要把这 $m$ 个映射合在一起即可.

然后用倍增的思想来处理 $k$ 次操作序列.

代码与上面非常的相似.