AGC044C Strange Dance

比较简单的一个题。我上来就直接考虑分块了，观察一下可以发现任意进行操作 $\bmod 3$ 之后的序列是三个数不断重复出现，而同理 $\mod 3^k$ 也一样。所以考虑把最后 $3^{n/2}$ 位单独考虑，$3^{\frac {3n}2}$ 是个可以通过的复杂度！

同时可以发现，在序列中低 $n/2$ 位是一个固定数的高位一定也形成了一个 $3^{n/2}$ 长的序列。我们可以维护这个序列，最后把两部分拼起来就行了。

对每次交换操作，对低 $n/2$ 执行交换，并且把每个位置对应的高 $n/2$ 位通过打标记的方式交换。

对加 $1$ 操作，可以发现只有低 $n/2$ 位全为 $1$ 的数才需要被加一，因此实际上只有一个高 $n/2$ 位的序列需要拿出来进行修改，单独对它修改即可。

这样复杂度就是 $O(3^{3n/2})$ 的，可以通过。

事实上完全没必要分块！之前联合省选考过这个东西，可以把所有数的三进制从低到高按位插入到 Trie 中。交换 $1,2$ 可以直接通过打 lazy tag 的方式维护。对于 $+1$ 操作，对最低位来讲本质上做了个 $0,1,2$ 的轮换，且轮换完后这个操作只会对 $2 \to 0$ 的这个子树造成影响，因此可以递归下去进行 $+1$ 操作。

这个东西看起来就和那个分块用到的性质差不多，但是复杂度是 $O(3^n + n|T|)$ ，更加优秀。

cpp

#include "bits/stdc++.h"
#include "atcoder/all"
using namespace std;
#define fi first
#define se second
#define vi vector<int>
#define pb push_back
#define eb emplace_back
#define pii pair<int,int>
#define mp make_pair
#define rep( i , a , b ) for( int i = (a) , i##end = b ; i <= i##end ; ++ i )
#define per( i , a , b ) for( int i = (a) , i##end = b ; i >= i##end ; -- i )
#define mem( a ) memset( a , 0 , sizeof (a) )
#define all( x ) x.begin() , x.end()
//#define int long long
// #pragma GCC optimize(2)
typedef long long ll;
const int MAXN = 1e6 + 10;
const int P = 1e9 + 7;
int n , q , lef;
const int B = 729;
char op[MAXN];
int idx[740] , rev[740];
int ts[740][740];

int trs[MAXN];

int calc( int c ) {
    vi s3;
    while( c ) s3.pb( c % 3 ) , c /= 3;
    reverse( all( s3 ) );
    int as = 0;
    for( int x : s3 ) {
        x = ( x > 0 ? ( 3 ^ x ) : 0 );
        as = as * 3 + x;
    }
    return as;
}

void pd( int x ) {
    if( rev[x] ) {
        rep( i , 0 , lef - 1 ) {
            ts[x][i] = trs[ts[x][i]];
        }
        rev[x] = 0;
    }
}

int ans[MAXN];

void solve() {
    rep( i , 1 , 540000 ) trs[i] = calc( i );
    // cout << trs[46] << endl;
    cin >> n;
    int N = 1;
    rep( i , 1 , n ) N = N * 3;
    scanf("%s",op + 1);
    q = strlen( op + 1 );
    if( n <= 7 ) {
        rep( i , 0 , N - 1 ) idx[i] = i;
        rep( i , 1 , q ) {
            if( op[i] == 'R' ) {
                rep( k , 0 , N - 1 ) idx[k] = ( idx[k] + 1 ) % N;
            } else {
                rep( k , 0 , N - 1 ) idx[k] = trs[idx[k]];
            }
        }
        rep( k , 0 , N - 1 ) printf("%d ",idx[k]); puts("");
        return;
    }
    rep( i , 0 , B - 1 ) idx[i] = i;
    lef = 1;
    rep( i , 7 , n ) lef *= 3;
    rep( i , 0 , B - 1 ) rep( j , 0 , lef - 1 ) ts[i][j] = j;
    rep( i , 1 , q ) {
        if( op[i] == 'R' ) {
            int ps = 0;
            rep( k , 0 , B - 1 ) if( idx[k] == B - 1 ) ps = k;
            pd( ps );
            rep( j , 0 , lef - 1 ) ts[ps][j] = ( ts[ps][j] + 1 ) % lef;
            rep( j , 0 , B - 1 ) idx[j] = ( idx[j] + 1 ) % B;
        } else {
            rep( k , 0 , B - 1 ) {
                idx[k] = trs[idx[k]];
                rev[k] ^= 1;
            }
        }
    }
    rep( i , 0 , B - 1 ) {
        pd( i );
        rep( j , 0 , lef - 1 ) {
            ans[j * B + i] = idx[i] + ts[i][j] * B;
        }
    }
    rep( i , 0 , N - 1 ) printf("%d ",ans[i]);
}

signed main() {
//	 freopen("in","r",stdin);
	// freopen("out","w",stdout);
	// int T;cin >> T;while( T-- ) solve();
	solve();
}