分享一下蒟蒻我的奇葩做法，因为不会dp……

这道题第一眼看便想到参考P1242 新汉诺塔的递归移圆盘的方法，在递归的过程中判断一下优先级就可以了，模拟即可。

20分的做法：

#include<iostream>
#include<cstdio>
using namespace std;
const int maxn = 50;
int n, last;
int pos[maxn], rnk[50], first[5], stk[4][maxn];
long long ans;
bool check()
{
    for(int i=2; i<=n; i++)
        if(pos[i] != pos[i-1] || (pos[i] == 1 || pos[i-1] == 1)) return false;
    return true;
}
void getRnk(int x, int &a, int &b)
{
    a = x / 10;
    b = x % 10;
}
void dfs()
{
    if(check()) return;
    for(int i=1; i<=6; i++)
    {
        int a, b;
        getRnk(rnk[i], a, b);
        if(stk[a][0] && stk[a][stk[a][0]] != last && (stk[a][stk[a][0]] < stk[b][stk[b][0]] || !stk[b][0]))
        {
            last = stk[a][stk[a][0]--];
            stk[b][++stk[b][0]] = last;
            pos[last] = b;
            dfs();
            break;
        }
    }
    ans++;
}
int main()
{
    scanf("%d", &n);
    for(int i=1; i<=n; i++) pos[i] = 1;
    for(int i=1; i<=6; i++)
    {
        char tmp[3];
        scanf("%s", tmp+1);
        int now = int(tmp[1]-'A'+1)*10 + int(tmp[2]-'A'+1);
        rnk[i] = now;
    }
    for(int i=1; i<=n; i++) stk[1][++stk[1][0]] = n-i+1;
    dfs();
    printf("%d", ans);
    return 0;
}

但是面对接近$10^{18}$的答案范围，显然在递归过程中会MLE——所以自然要打表找规律啦

因为总的顺序数就是6！，即720种可能情况，用1代表AB，2代表AC，3代表BA，4代表BC，5代表CA，6代表CB，枚举一下1，2，3，4，5，6的全排列，我们发现：

n=3时有7, 9, 17这三种答案
n=4时有15, 27, 53这三种答案
n=5时有31, 81, 161这三种答案

所以对于n，答案就是$2^n-1$, $3^{n-1}$, $2*3^{n-1}-1$中的某一个，根据n=3时的结果得出mark数组.

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 50;
int n, last;
int a[10], p[10];
int mark[721] =
{
/*
看一下对于AB, AC, BA, BC, CA, CB的
每一个排列对应的答案是哪一个
1, 2, 3分别表示2^n-1, 3^(n-1), 2*3^(n-1)-1
*/
    3, 3, 3, 3, 3, 3, 1, 2, 1, 1, 
    2, 2, 3, 3, 1, 1, 3, 1, 3, 3, 
    2, 2, 3, 2, 3, 3, 3, 3, 3, 3, 
    3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 
    3, 3, 3, 3, 3, 3, 3, 3, 1, 2, 
    1, 1, 2, 2, 1, 2, 1, 1, 2, 2, 
    1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 
    2, 2, 3, 3, 1, 1, 3, 1, 3, 3, 
    3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 
    3, 1, 3, 3, 1, 1, 3, 3, 2, 2, 
    3, 2, 3, 3, 3, 3, 3, 3, 2, 2, 
    2, 2, 2, 2, 3, 2, 3, 3, 2, 2, 
    3, 1, 3, 3, 1, 1, 3, 2, 3, 3, 
    2, 2, 3, 3, 3, 3, 3, 3, 1, 1, 
    2, 2, 1, 2, 3, 1, 3, 3, 1, 1, 
    3, 1, 3, 3, 1, 1, 3, 3, 3, 3, 
    3, 3, 1, 1, 1, 1, 1, 1, 3, 2, 
    3, 3, 2, 2, 3, 2, 3, 3, 2, 2, 
    3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 
    2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 
    3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 
    3, 3, 3, 3, 3, 3, 1, 1, 2, 2, 
    1, 2, 1, 1, 1, 1, 1, 1, 2, 2, 
    2, 2, 2, 2, 1, 2, 1, 1, 2, 2, 
    3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 
    3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 
    3, 3, 3, 3, 3, 1, 3, 3, 1, 1, 
    3, 1, 3, 3, 1, 1, 3, 3, 3, 3, 
    3, 3, 1, 1, 1, 1, 1, 1, 3, 3, 
    3, 3, 3, 3, 3, 1, 3, 3, 1, 1, 
    3, 3, 3, 3, 3, 3, 3, 3, 1, 1, 
    3, 1, 3, 3, 3, 3, 3, 3, 3, 3, 
    3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 
    3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 
    3, 3, 1, 1, 1, 1, 1, 1, 3, 3, 
    1, 1, 3, 1, 3, 3, 1, 1, 3, 1, 
    1, 2, 1, 1, 2, 2, 1, 2, 1, 1, 
    2, 2, 1, 1, 1, 1, 1, 1, 2, 2, 
    2, 2, 2, 2, 3, 2, 3, 3, 2, 2, 
    3, 2, 3, 3, 2, 2, 3, 3, 3, 3, 
    3, 3, 2, 2, 2, 2, 2, 2, 1, 2, 
    1, 1, 2, 2, 3, 2, 3, 3, 2, 2, 
    1, 1, 3, 3, 1, 3, 2, 2, 2, 2, 
    2, 2, 1, 1, 1, 1, 1, 1, 3, 3, 
    3, 3, 3, 3, 1, 1, 3, 3, 1, 3, 
    1, 1, 3, 3, 1, 3, 2, 2, 2, 2, 
    2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 
    2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 
    3, 3, 1, 1, 3, 1, 3, 3, 3, 3, 
    3, 3, 1, 1, 1, 1, 1, 1, 3, 1, 
    3, 3, 1, 1, 3, 3, 3, 3, 3, 3, 
    3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 
    3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 
    3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 
    3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 
    3, 3, 1, 1, 1, 1, 1, 1, 3, 3, 
    3, 3, 3, 3, 1, 1, 3, 3, 1, 3, 
    1, 1, 3, 3, 1, 3, 3, 1, 3, 3, 
    1, 1, 3, 3, 3, 3, 3, 3, 3, 3, 
    3, 3, 3, 3, 1, 1, 3, 3, 1, 3, 
    3, 3, 2, 2, 3, 2, 3, 3, 3, 3, 
    3, 3, 2, 2, 2, 2, 2, 2, 3, 2, 
    3, 3, 2, 2, 1, 1, 2, 2, 1, 2, 
    1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 
    2, 2, 1, 2, 1, 1, 2, 2, 3, 3, 
    3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 
    3, 3, 1, 1, 3, 1, 3, 3, 1, 1, 
    3, 1, 2, 2, 2, 2, 2, 2, 2, 2, 
    2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 
    2, 2, 2, 2, 2, 2, 3, 2, 3, 3, 
    2, 2, 1, 2, 1, 1, 2, 2, 3, 3, 
    1, 1, 3, 1, 2, 2, 2, 2, 2, 2, 
};
long long ans;

int cal(char *tmp)
{
    if(tmp[1] == 'A' && tmp[2] == 'B') return 1;
    if(tmp[1] == 'A' && tmp[2] == 'C') return 2;
    if(tmp[1] == 'B' && tmp[2] == 'A') return 3;
    if(tmp[1] == 'B' && tmp[2] == 'C') return 4;
    if(tmp[1] == 'C' && tmp[2] == 'A') return 5;
    if(tmp[1] == 'C' && tmp[2] == 'B') return 6;
}
int cantor(int now[10])
{   //康拓展开求出输入的排列在全排列中排第几
    int cnt = 0, res = 0;
    bool vis[15];
    memset(vis, 0, sizeof(vis));
    for(int i=1; i<=6; i++)
    {
        int small = 0;
        vis[now[i]] = true;
        for(int j=1; j<now[i]; j++)
        {
            if(!vis[j]) small++;
        }
        res += small*p[6-i];
    }
    return res;
}
void solve1()
{
    ans = 1;
    for(int i=1; i<=n; i++)
        ans *= 2;
    ans--;
}
void solve2()
{
    ans = 1;
    for(int i=1; i<n; i++)
        ans *= 3;
}
void solve3()
{
    ans = 1;
    for(int i=1; i<n; i++)
        ans *= 3;
    ans = ans*2 - 1;
}
int main()
{
    scanf("%d", &n);
    p[0] = 1;
    for(int i=1; i<=9; i++) p[i] = p[i-1]*i;
    for(int i=1; i<=6; i++)
    {
        char tmp[3];
        scanf("%s", tmp+1);
        a[i] = cal(tmp);
    }
    int loc = cantor(a);
    if(mark[loc] == 1) solve1();
    if(mark[loc] == 2) solve2();
    if(mark[loc] == 3) solve3();
    printf("%lld", ans);
    return 0;
}