题目链接：https://atcoder.jp/contests/agc044/tasks/agc044_c

题目大意：给一个大小为 $3^{n}$ 的数组，下标为 $0,1,2,…,3^n -1$ ，一开始 $a_{i}=i$，然后有两个操作：

  1. 令 $a’_{j}=a_{i}$ ，其中 $j$ 是 $i$ 三进制中如果是 $2$ 变成 $1$ ，是 $1$ 变成 $2$ 后的结果。
  2. 令 $a$ 数组循环右移一格。

问给定操作序列后的数组的逆是啥。

做法

不妨分层考虑：

对于一个 $3^{k}$ 的元件，假如我们已经知道其在操作后进来了多少个数字，出去了什么数字，以及剩下的数字的排布，显然能够类似归并一样的处理出 $3^{k+1}$ 。

然后就做完了。

时间复杂度：$O(n*|S|+3^{n})$

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
#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int SN = 6e5 + 5;
const int N = 2e5 + 5;
const int L = 21;
int n, l, f3[L];
char st[N];
void get_char_array(char *s){
    static char ss[N];
    cin >> ss;
    static int len;
    len = strlen(ss);
    memcpy(s + 1, ss, sizeof(char) * len);
}
int nex[][3] = {{1, 2, -1}, {2, -1, 1}};
int ord[][3]= {{0, 1, 2}, {0, 2, 1}};
int be[SN];
void solve(){
    cin >> l;
    get_char_array(st);
    n = strlen(st + 1);
    f3[0] = 1;for(int i = 1; i <= l; i++) f3[i] = f3[i - 1] * 3;
    vector<int> in, out, res;
    vector<int> mov;
    int final_type;
    {
        int tmp = 0;
        int type = 0;
        for(int i = 1; i <= n; i++){
            if(st[i] == 'S') type ^= 1;
            else{
                out.push_back(tmp);
                tmp++;
                mov.push_back(type);
            }
        }
        res.push_back(tmp);
        final_type = type;
    }
    for(int i = 1; i <= l; i++){//merge
        vector<int> tmp_out = out, tmp_res = res;
        out.clear();
        res.clear();
        vector<int> now[3];
        for(int j = 0; j < mov.size(); j++){
            int type = mov[j];
            int o = tmp_out[j];
            for(int t = 0; t <= 2; t++){
                int ne = nex[type][t], x;
                if(o < f3[i - 1]) x = t * f3[i - 1] + o;
                else if(!t) x = o - f3[i - 1] + f3[i];
                else x = now[t][o - f3[i - 1]];
                if(ne == -1) out.push_back(x);
                else now[ne].push_back(x);
            }
        }
        for(int t = 0; t <= 2; t++){
            int tt = ord[final_type][t];
            for(auto x : tmp_res){
                if(x < f3[i - 1]) res.push_back(tt * f3[i - 1] + x);
                else if(!tt) res.push_back(x - f3[i - 1] + f3[i]);
                else res.push_back(now[tt][x - f3[i - 1]]);
            }
        }
    }
    {
        for(auto &x : res){
            while(x >= f3[l]) x = out[x - f3[l]];
        }
    }
    for(int i = 0; i < f3[l]; i++) be[res[i]] = i;
    for(int i = 0; i < f3[l]; i++) cout << be[i] << " ";
    cout << "\n";
}
int main(){
    solve();
    return 0;
}
Trie 做法

这都能字典树，厉害。

考虑将原来的数组用字典树表示。

首先注意到一个事情，第一个操作是全局下标变换，这在外边打个标记就行了。

而第二个操作全局下标 $+1$ 在传统字典树上很难实现，但是如果字典树是从低到高建的呢？那就非常简单了，处理进位的那棵子树就行了，时间复杂度：$O(n)$ 。

综上，时间复杂度为：$O(n*|S|+3^n)$ 。