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;
}
思路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\) 次操作序列.
代码与上面非常的相似.
标签：...,int,P6148,矩阵,Swapity,leq,Swap,bmatrix,vdots From： https://www.cnblogs.com/wyl123ly/p/18464752