\(\mathcal{Description}\)

  Link（削弱版）.

  \(n\) 张纸叠在一起对折 \(k\) 次，然后从上到下为每层的正反两面写上数字，求把纸重新摊平后每张纸上的数字序列。

  \(n\le10\)，\(k\le19\)。

\(\mathcal{Solution}\)

  模拟摊平操作，对于每一层维护一个双向链表（实际指针的方向并不重要，不要纠结两个叫 pre 的指针相互指的问题），每次把上一半的反向接到下一半即可。

  复杂度 \(\mathcal O(n2^k)\)，瓶颈在 IO。

#include <cstdio>
#include <vector>
#include <assert.h>

typedef unsigned long long ULL;

inline char fgc () {
    static char buf[1 << 17], *p = buf, *q = buf;
    return p == q && ( q = buf + fread ( p = buf, 1, 1 << 17, stdin ), p == q ) ? EOF : *p ++;
}

inline ULL rint () {
    ULL x = 0; char s = fgc ();
    for ( ; s < '0' || '9' < s; s = fgc () );
    for ( ; '0' <= s && s <= '9'; s = fgc () ) x = x * 10 + ( s ^ '0' );
    return x;
}

inline void wint ( const ULL x ) {
    if ( 9 < x ) wint ( x / 10 );
    putchar ( x % 10 ^ '0' );
}

const int MAXN = 10, MAXK = 19, MAXP = 1 << MAXK << 1, MAXL = MAXN << MAXK << 1;
int n, K, perL, L, p[MAXL + 5];
int pre[MAXP + 5], suf[MAXP + 5], lef[MAXP + 5], rig[MAXP + 5];
std::vector<int> paper[MAXN + 5], fold;

namespace Generator {

const int threshold = 10000000;
ULL k1,k2;

ULL xorShift128Plus () {
    ULL k3 = k1, k4 = k2;
    k1 = k4, k3 ^= k3 << 23;
    k2 = k3 ^ k4 ^ ( k3 >> 17 ) ^ ( k4 >> 26 );
    return k2 + k4;
}

void gen ( int n, int k, ULL _k1, ULL _k2){
    k1 = _k1, k2 = _k2;
    int _len = 2 * n * ( 1 << k );
    for ( int i = 1; i <= _len; i ++ )
     p[i] = xorShift128Plus () % threshold + 1;
}

};

inline void initFold ( std::vector<int>& res ) {
    int up = perL;
    for ( int i = up; i; -- i ) {
        lef[i] = rig[i] = up - i + 1;
        pre[i] = suf[i] = 0;
    }
    while ( up > 2 ) {
        int mid = up >> 1;
        for ( int i = mid + 1; i <= up; ++ i ) {
            int j = mid * 2 + 1 - i;
            if ( !suf[lef[i]] ) {
                assert ( !suf[lef[j]] );
                suf[lef[i]] = lef[j], suf[lef[j]] = lef[i];
            } else {
                assert ( !pre[lef[i]] && !pre[lef[j]] );
                pre[lef[i]] = lef[j], pre[lef[j]] = lef[i];
            }
            lef[j] = rig[i];
        }
        up = mid;
    }
    int i = lef[1], las = 0;
    for ( int i = lef[2], las = 0; ; ) {
        res.push_back ( i );
        if ( i == rig[2] ) break;
        int nxt = suf[i] ^ las ? suf[i] : pre[i];
        las = i, i = nxt;
    }
    for ( int i = lef[1], las = 0; ; ) {
        res.push_back ( i );
        if ( i == rig[1] ) break;
        int nxt = suf[i] ^ las ? suf[i] : pre[i];
        las = i, i = nxt;
    }
}

int main () {
     freopen ( "folding.in", "r", stdin );
     freopen ( "folding.out", "w", stdout );
    for ( int T = rint (), type = rint (); T --; ) {
        n = rint (), K = rint (), perL = 1 << K << 1, L = n * perL;
        if ( !type ) for ( int i = 1; i <= L; ++ i ) p[i] = rint ();
        else {
            ULL k1 = rint (), k2 = rint ();
            Generator::gen ( n, K, k1, k2 );
        }
        for ( int i = 1; i <= L; ++ i ) { // attention that K>0.
            int r = ( i - 1 ) % ( n << 2 ) + 1;
            if ( r <= n << 1 ) {
                paper[n - ( r - 1 ) / 2].push_back ( p[i] );
            } else {
                paper[( r - ( n << 1 ) - 1 ) / 2 + 1].push_back ( p[i] );
            }
        }
        initFold ( fold );
        ULL ans = 0;
        for ( int i = 1, id = 0; i <= n; ++ i ) {
            for ( int j = 0; j < perL; ++ j ) {
                ans ^= 1ll * ++ id * paper[i][fold[j] - 1];
            }
            paper[i].clear ();
        }
        wint ( ans ), putchar ( '\n' );
    }
    return 0;
}

  为什么这种大模拟兔子会想到去找规律……

  关键是死也没找出来！

  联赛难度联赛难度啊你姿势摆对啊喂 qwq！