自动搬运

查看原文

来自洛谷，原作者为

	xusj **

搬运于2025-08-24 21:14:53，当前版本为作者最后更新于2025-08-11 16:58:32，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

B3761 题解

水题

题目大意：

给定对三角魔方的若干次操作，以及 $a$, $b$, 求进行 $a^b$ 次这些操作后魔方的状态。

思路分析：

首先观察数据范围，有 $1 \le a,b \le 10^3$，直接暴力枚举不可行。考虑到魔方是按照固定的若干次操作进行的，其必定会进入一个循环，下面给出简略的证明：

• 已知魔方的状态数是有限的；
• 根据抽屉原理，必定存在两次操作使得状态重复，即其会有一个循环；
• 最后，要确定初始状态在循环内。对此，假设初始状态不在循环内，则存在两种不同状态到达同一种状态，由于每种操作都有唯一确定的逆操作，矛盾，故初始状态在循环内。

由此，我们可以暴力进行操作，并判断是否与初始状态相同，同时用 $cnt$ 统计循环的操作次数，使用快速幂求得 $a^b \bmod b$ 最后再跑一遍暴力即可。

具体实现

• 根据题意，预处理 $U3,U5,U7$,$R3,R5,R7$,$D3,D5,D7$ 操作，注意到 $U1,R1,D1$ 可跳过，其对于魔方的状态无影响；
• 不断进行操作，求得循环长度；
• 快速幂求得剩余操作数；
• 求解最终答案。

详细解释放代码里了。

快速幂：【模板】快速幂

附上代码

#include<bits/stdc++.h> 
using namespace std;
int a, b, c[20], d[20], cnt = 0;    //a,b为题中给定，c为原数组，d为进行操作的数组 
char mp[20] = {' ', 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P'};
//数字易于操作,mp为数字1-16与'A'-'P'的映射 
string op;    //给定若干操作，不知操作数，使用string 
void s(int x, int y) {swap(d[x], d[y]);} //交换，减少码量
//以下为9种操作，注意按题中箭头顺序
void u3() {s(11, 5); s(12, 11); return;}
void u5() {s(6, 2); s(7, 6); s(13, 7); s(14, 13); return;}
void u7() {s(3, 1); s(4, 3); s(8, 4); s(9, 8); s(15, 9); s(16, 15); return;}
void r3() {s(3, 4); s(2, 3); return;}
void r5() {s(8, 9); s(7, 8); s(6, 7); s(5, 6); return;}
void r7() {s(15, 16); s(14, 15); s(13, 14); s(12, 13); s(11, 12); s(10, 11); return;}
void d3() {s(15, 14); s(9, 15); return;}
void d5() {s(13, 12); s(7, 13); s(8, 7); s(4, 8); return;}
void d7() {s(11, 10); s(5, 11); s(6, 5); s(2, 6); s(3, 2); s(1, 3); return;}
bool f() {
	for (int x = 1; x <= 16; x++)
	  if (c[x] != d[x]) return false;
	return true;
}    //判断是否与初始状态相同 
int ksm(int x, int y, int mod) {
	int ans = 1, base = x;
	while (y > 0) {
		if (y & 1) ans = ans * base % mod;
		base = base * base % mod;
		y >>= 1;
	}
	return ans % mod;
}    //快速幂求剩余操作数 
void rotate() {
	for (int i = 0; i < (int)op.size(); i += 2) {
		//可省略op[i+1] == '1'的情况
		if (op[i] == 'U') {
			if (op[i + 1] == '3') u3();
			else if (op[i + 1] == '5') u5();
			else if (op[i + 1] == '7') u7();
		}
		else if (op[i] == 'R') {
			if (op[i + 1] == '3') r3();
			else if (op[i + 1] == '5') r5();
			else if (op[i + 1] == '7') r7();
		}
		else if (op[i] == 'D') {
			if (op[i + 1] == '3') d3();
			else if (op[i + 1] == '5') d5();
			else if (op[i + 1] == '7') d7();
		}
	}
}    //转动魔方 
int main() {
	cin >> op >> a >> b;
	for (int i = 1; i <= 16; i++) c[i] = d[i] = i;  //初始状态 
	while (cnt == 0 || !f()) cnt++, rotate();    //求解循环长度 
	int res = ksm(a, b, cnt);    //快速幂求解剩余次数 
	for (int k = 1; k <= res; k++) rotate();    //直接求出答案 
	for (int i = 1; i <= 16; i++) cout << mp[d[i]];    //输出结果 
	return 0;
}