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

SqrtOne · 2026-07-19 19:18:34 · 题解

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

题目大意

对于一个三角魔方，给定一个操作序列和两个参数 a, b，求进行 a^b 次操作后魔方的状态。

题目分析

显而易见，这是一道模拟题，我们可以直接模拟魔方的操作。暴力写法可以获得 50 分。

约定用 0-index 的字符串 S 表示魔方从上到下、从左到右标有的字母。例如，初始状态表示为 `ABCDEFGHIJKLMNOP`。

显然，U1, R1, D1 操作是不会对魔方产生影响的，可以直接跳过不处理。
我们不妨以操作 U3 为例：
原先的 S_4, S_{10}, S_{11} 在操作后变成了 S_{10}, S_{11}, S_4。那么，我们可以写出以下代码：

swap(s[4], s[10]);
swap(s[10], s[11]);

其他操作同理。注意每个操作的方向和顺序，实在不理解的可以自己尝试画图。

:::success[参考代码]

void change (string &s, char c, int u) {
    if (u == 1) return;

    if (c == 'R') {
        if (u == 3) 
            for (int i = 3; i > 1; --i)  swap(s[i], s[i - 1]); // 由于操作对象都在同一行，可以使用循环简化代码
        if (u == 5) 
            for (int i = 8; i > 4; --i)  swap(s[i], s[i - 1]);
        if (u == 7) 
            for (int i = 15; i > 9; --i) swap(s[i], s[i - 1]);
    }

    if (c == 'U') {
        if (u == 3) {
            swap(s[4], s[10]);  swap(s[10], s[11]);
        }

        if (u == 5) {
            swap(s[1], s[5]);   swap(s[5], s[6]);
            swap(s[6], s[12]);  swap(s[12], s[13]);
        }

        if (u == 7) {
            swap(s[0], s[2]);   swap(s[2], s[3]);
            swap(s[3], s[7]);   swap(s[7], s[8]);
            swap(s[8], s[14]);  swap(s[14], s[15]);
        }
    }

    if (c == 'D') {
        if (u == 3) {
            swap(s[13], s[14]); swap(s[14], s[8]);
        }

        if (u == 5) {
            swap(s[11], s[12]); swap(s[12], s[6]);
            swap(s[6], s[7]);   swap(s[7], s[3]);
        }

        if (u == 7) {
            swap(s[9], s[10]);  swap(s[10], s[4]);
            swap(s[4], s[5]);   swap(s[5], s[1]);
            swap(s[1], s[2]);   swap(s[2], s[0]);
        }
    }
}

:::

但是有个问题：注意到 1 \le a, b \le 10^3，直接枚举只能获得 50 分，需要考虑优化。

魔方的操作结果会呈周期循环出现，在本题中也是如此。以下是简要证明：

:::info[证明]

我们可以用抽屉原理来严格证明：

1. 构造一个状态序列：从初始状态 S_0 开始，连续执行同一个操作序列 T。我们得到一个无限长的状态序列：S_0, S_1 = T(S_0), S_2 = T(S_1), \dots。

2. 应用抽屉原理：由于状态总数只有有限的 16! 种，但这个序列可以无限延长。因此，在这个无限序列中，必然至少有两个状态是相同的。也就是说，存在 i < j，使得 S_i = S_j。

3. 确定循环起点：因为操作 T 是可逆的（有逆操作），我们可以从 S_i = S_j 这个等式出发。对等式两边同时施加 i 次逆操作，就能得到 S_0 = S_{j-i}。

4. 结论：这意味着，从初始状态出发，经过 j-i 次操作后，状态首次回到了初始状态 S_0。从此以后，状态序列就会以 j-i 为周期，在 S_0, S_1, \dots, S_{j-i-1} 这些状态之间无限循环下去。

:::

所以，我们可以求出魔方在第一次回到初始状态时的操作次数 k，则最后的结果等效于直接求操作 a^b \bmod k 次后的结果。

需要前置知识——快速幂。

附上代码：

:::success[AC Code]

// OwO
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define st first
#define nd second

string S = "ABCDEFGHIJKLMNOP"; // 初始序列，用于对比
string T = "ABCDEFGHIJKLMNOP"; // 实际被操作序列
string op; // 操作序列
int a, n, mod = 0;

void change (string &s, char c, int u);
int fpow (int a, int n);

signed main () {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> op >> a >> n;

    while (true) {
        for (int i = 0; i < op.size(); i += 2) {
            change(T, op[i], op[i + 1] - '0');
        }
        mod ++;
        if (T == S) break;
    }

    int k = fpow(a, n);
    while (k--) {
        for (int i = 0; i < op.size(); i += 2) {
            change(T, op[i], op[i + 1] - '0');
        }
    }
    cout << T << endl;
    return 0;
}

void change (string &s, char c, int u) {
    if (u == 1) return;

    if (c == 'R') {
        if (u == 3) 
            for (int i = 3; i > 1; --i)  swap(s[i], s[i - 1]);
        if (u == 5) 
            for (int i = 8; i > 4; --i)  swap(s[i], s[i - 1]);
        if (u == 7) 
            for (int i = 15; i > 9; --i) swap(s[i], s[i - 1]);
    }

    if (c == 'U') {
        if (u == 3) {
            swap(s[4], s[10]);  swap(s[10], s[11]);
        }

        if (u == 5) {
            swap(s[1], s[5]);   swap(s[5], s[6]);
            swap(s[6], s[12]);  swap(s[12], s[13]);
        }

        if (u == 7) {
            swap(s[0], s[2]);   swap(s[2], s[3]);
            swap(s[3], s[7]);   swap(s[7], s[8]);
            swap(s[8], s[14]);  swap(s[14], s[15]);
        }
    }

    if (c == 'D') {
        if (u == 3) {
            swap(s[13], s[14]); swap(s[14], s[8]);
        }

        if (u == 5) {
            swap(s[11], s[12]); swap(s[12], s[6]);
            swap(s[6], s[7]);   swap(s[7], s[3]);
        }

        if (u == 7) {
            swap(s[9], s[10]);  swap(s[10], s[4]);
            swap(s[4], s[5]);   swap(s[5], s[1]);
            swap(s[1], s[2]);   swap(s[2], s[0]);
        }
    }
}

int fpow (int a, int n) {
    if (n == 0) return 1;
    int x = fpow(a, n / 2);
    return x * x % mod * (n % 2 ? a : 1) % mod;
}

:::