P6148 [USACO20FEB] Swapity Swapity Swap S

wyl123ly / 2024-10-15 / 原文

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:$

#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;
}