w wyl123ly 的博客
MD

P6148 Swapity Swapity Swap S

4 KB 2026.10.11 原文件

P6148 [USACO20FEB] Swapity Swapity Swap S

Farmer John 的 头奶牛()站成一排。对于每一个 ,从左往右数第 头奶牛的编号为 。

Farmer John 想到了一个新的奶牛晨练方案。他给奶牛们 对整数 ,其中 。他让她们重复以下包含 个步骤的过程 ()次:

对于从 到 的每一个 :

  • 当前从左往右数在位置 的奶牛序列反转她们的顺序。
  • 当奶牛们重复这一过程 次后,请对每一个 输出从左往右数第 头奶牛的编号。

思路1:

首先看暴力,暴力 ,非常的去世。

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

初始答案矩阵:

那么对于一次交换 的转移,我们可以构造出转移矩阵:

其中 的子矩阵是:

其中副斜对角线上的的值全为 .

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

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

但是我们发现 ,也就是说我们的转移矩阵的大小要是 的大小,不 也得 .

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

则我们可以把这个矩阵压缩成 的矩阵:

第 行的元素代表了原转移矩阵第 行中的 在第几列.

那么我们转移矩阵的相乘就可以变成: (其中 是答案矩阵, 是转移矩阵.)

矩阵的自乘就会变为:

这样看就很简单了,我们定义 MATRIX 结构体,在里面重载运算符实现 运算即可.

#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

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

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

对于每 次操作,我们设为 为一次映射,则对于一次操作序列的映射效果 ,我们有:

其中 表示初始状态.

我们用 来表示一次操作序列中的一次操作,那么我们只需要把这 个映射合在一起即可.

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

代码与上面非常的相似.