ABC 13 D - 阿弥陀 ( Doubling )

D: 阿弥陀 - AtCoder Beginner Contest 013 | AtCoder
Without the variable D, we can simulate the process by swapping the numbers where edges exist, since making an edge on the bottom is equivalent to swapping the index of the two lines. We can map where each starting index will eventually go to, and if we let t[ i ] be the terminal of i, we will find that the ultimate answer is t^D[ i ], and since it is the form of power, we can use doubling to pre-calculate all the 2^n ≤ d powers of t(). Overall time complexity O( n lg d + m ).

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
const int MAXM = 2e5 + 5;
const int MAXD = 1e9 + 9;
const int LGN = 31; // 2 ^ 30 > 1e9
 
int n, m, d;
int a[ MAXM ];
 
int t[ LGN ][ MAXN ]; // terminal node when starting from node j, after playing 2 ^ i games
 
void solve(){
    for(int i = 1; i <= n; ++i)
        t[ 0 ][ i ] = i; // if there are no horizontal lines, it will go to itself
    for(int i = m - 1; i >= 0; --i) // lines are given from top to bottom
        swap<int>( t[ 0 ][ a[ i ] ], t[ 0 ][ a[ i ] + 1 ] );
    for(int i = 1; i < LGN; ++i)
        for(int j = 1; j <= n; ++j){
            int k = t[ i - 1 ][ j ];
            t[ i ][ j ] = t[ i - 1 ][ k ];
        }
    for(int i = 1; i <= n; ++i){
        int u = i;
        int td = d;
        for(int k = 0; k < LGN; ++k){
            if( td & 1 ) u = t[ k ][ u ];
            td >>= 1;
        }
        printf("%d\n", u);
    }
}
 
int main(){
    scanf("%d%d%d", &n, &m, &d);
    for(int i = 0; i < m; ++i)
        scanf("%d", &a[ i ]);
    solve();
    return 0;
}