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

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

20分的做法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#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;
}

但是面对接近101810^{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，答案就是2n−12^n-1, 3n−13^{n-1}, 2∗3n−1−12*3^{n-1}-1中的某一个，根据n=3时的结果得出mark数组.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
#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;
}