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

· · 题解

题目传送门

思路如下： 首先观察，发现 U1， D1， R1 操作后不改变，无需处理；
然后，在代码中用一个字符串 c 来表示这个“金字塔”，c_i 代表处在 ASCII 码为 i+64 的字母的位置，手推后不难得出 make 函数：

void make(string opt) {//opt是操作类型
    char t;
    if(opt=="R3") {
        t=c[1];
        c[1]=c[3];
        c[3]=c[2];
        c[2]=t;
    }
    else if(opt=="R5") {
        t=c[4];
        c[4]=c[8];
        c[8]=c[7];
        c[7]=c[6];
        c[6]=c[5];
        c[5]=t;
    }
    else if(opt=="R7") {
        t=c[9];
        c[9]=c[15];
        c[15]=c[14];
        c[14]=c[13];
        c[13]=c[12];
        c[12]=c[11];
        c[11]=c[10];
        c[10]=t;
    }
    else if(opt=="D3") {
        t=c[13];
        c[13]=c[14];
        c[14]=c[8];
        c[8]=t;
    }
    else if(opt=="D5") {
        t=c[11];
        c[11]=c[12];
        c[12]=c[6];
        c[6]=c[7];
        c[7]=c[3];
        c[3]=t;
    }
    else if(opt=="D7") {
        t=c[9];
        c[9]=c[10];
        c[10]=c[4];
        c[4]=c[5];
        c[5]=c[1];
        c[1]=c[2];
        c[2]=c[0];
        c[0]=t;
    }
    else if(opt=="U3") {
        t=c[4];
        c[4]=c[10];
        c[10]=c[11];
        c[11]=t;
    }
    else if(opt=="U5") {
        t=c[1];
        c[1]=c[5];
        c[5]=c[6];
        c[6]=c[12];
        c[12]=c[13];
        c[13]=t;
    }
    else if(opt=="U7") {
        t=c[0];
        c[0]=c[2];
        c[2]=c[3];
        c[3]=c[7];
        c[7]=c[8];
        c[8]=c[14];
        c[14]=c[15];
        c[15]=t;
    }
}

而且，这道题 a,b \le 1000，略大，明显要用快速幂和试验规律，发现：对于每种操作，都会出现若干次操作后返回初始状态的情况，出现规律。
找到规律后，再使用快速幂使操作次数从原来的 a^b 变成了一个较小的数，之后再暴力即可。
AC记录

#include<bits/stdc++.h>
using namespace std;
int k;//k为循环节长度
string c="ABCDEFGHIJKLMNOP";
map<string,bool> mp;//记录这个状态存在过了没有
void make(string opt) {//opt是操作类型
    char t;
    if(opt=="R3") {
        t=c[1];
        c[1]=c[3];
        c[3]=c[2];
        c[2]=t;
    }
    else if(opt=="R5") {
        t=c[4];
        c[4]=c[8];
        c[8]=c[7];
        c[7]=c[6];
        c[6]=c[5];
        c[5]=t;
    }
    else if(opt=="R7") {
        t=c[9];
        c[9]=c[15];
        c[15]=c[14];
        c[14]=c[13];
        c[13]=c[12];
        c[12]=c[11];
        c[11]=c[10];
        c[10]=t;
    }
    else if(opt=="D3") {
        t=c[13];
        c[13]=c[14];
        c[14]=c[8];
        c[8]=t;
    }
    else if(opt=="D5") {
        t=c[11];
        c[11]=c[12];
        c[12]=c[6];
        c[6]=c[7];
        c[7]=c[3];
        c[3]=t;
    }
    else if(opt=="D7") {
        t=c[9];
        c[9]=c[10];
        c[10]=c[4];
        c[4]=c[5];
        c[5]=c[1];
        c[1]=c[2];
        c[2]=c[0];
        c[0]=t;
    }
    else if(opt=="U3") {
        t=c[4];
        c[4]=c[10];
        c[10]=c[11];
        c[11]=t;
    }
    else if(opt=="U5") {
        t=c[1];
        c[1]=c[5];
        c[5]=c[6];
        c[6]=c[12];
        c[12]=c[13];
        c[13]=t;
    }
    else if(opt=="U7") {
        t=c[0];
        c[0]=c[2];
        c[2]=c[3];
        c[3]=c[7];
        c[7]=c[8];
        c[8]=c[14];
        c[14]=c[15];
        c[15]=t;
    }
} 
int fpow(int a,int b) {//快速幂
    if(b==0) return 1;
    else if(b%2==0) return fpow((a%k)*(a%k)%k,b/2);
    else return (a%k)*fpow(a,b-1)%k;
}
int main() {
    string s;
    int n,m;
    cin>>s>>n>>m;
    for(int i=0;;i++) {
        if(!mp[c]) mp[c]=1;
        else {
            k=i;
            break;
        }
        string t="";
        for(int j=0;j<s.size()/2;j++) {//输入操作
            t="";
            t+=s[j*2];
            t+=s[j*2+1];
            make(t);
        }
    }
    int sum=fastpow(n%k,m);
    while(sum--) {
        string t="";
        for(int j=0;j<s.size()/2;j++) {
            t="";
            t+=s[j*2];
            t+=s[j*2+1];
            make(t);
        }
    }
    cout<<c;
    return 0;
}

附：这篇题解原本是在快一年前写的，只改了改部分幼稚的语言和丑陋的码风，望见谅。