题解：B3761 [信息与未来 2021] 三角魔方

xusj · 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;
}