题解：CF2172H Shuffling Cards with Problem Solver 68!

· · 题解

*2500 爽调半天。

好像没有我这种神奇做法的，或许太复杂了，感觉比较意识流。

钦定 n = 2^k。

通过观察/手摸样例发现，对于一个序列，交换次数达到 k 次必定回到原序列。

所以可以视作只交换 d\leftarrow t\bmod k 次。枚举从哪一个点洗牌，容易做到 O(n^2d) 。

考虑优化，由于每一个位置最终会变成哪一个位置是确定的，不需要每次都求，可以提前预处理出来。

于是可以做到 O(nd + n^2)。

紧接着，画图观察一下这个变化的性质：

对于 n = 8，进行 d = 1 或 d = 2 次操作之后会变成：

没看出来？没关系，打一个 n 更大的：

以此类推，得到一个结论：对于同一种颜色连续放在一起的，我们视作一个块。

每一个块内的点数刚好是 2^d，两个位置的间隔恰好也是 2^d，而块的数量就为 2^{k - d}。

这个东西有一个非常优美的性质。

考虑每次往后切一位牌之后，整个序列会发生什么变化：

不难发现，第一个块会变成最后一个块，并且第一个数变成这个块中的最后一个位置，剩下的块整体前移。

我们考虑快速维护这个东西。

对于比较从两个位置开始的大小，可以先将原序列哈希，然后二分找出第一个不一样的位置，比较大小。

但是每次整体挪每一个块的所有字符到后面来肯定是不现实的。

所以我们考虑对一个块整体考虑，每次只需要存这一个整块的哈希值，以及在对应的初始块中往后移动了多少个即可。

由于每次每个块总哈希值只变化一位，所以这是好做的。

现在做法变成，先对两个比较的位置二分出第一个不一样的块，再在不一样的块里面二分出第一个不一样的位置。

时间复杂度 O(n (\log 2^{d} + \log 2^{k - d})) = O(nk)，常数不大，有点难写，但是思路感觉挺具有启发性的。

:::success[Code]

struct Hash {
    std::vector <ui64> Ha, B; ui64 hb;

    inline i64 ask (i64 l, i64 r) noexcept {
        return Ha[r] - Ha[l - 1] * ppow[r - l + 1];
    }

    void insert (std::vector <i64>& A) noexcept {
        i64 v = 0; Ha.push_back (0), B.push_back (0);
        for (i32 i = 1; i <= rkuai * 2; i++)
            Ha.push_back (v = v * p + A[i]),
            B.push_back (A[i]);

        hb = ask (1, rkuai);/*记得把总哈希值处理一下*/
    }
} Ha[MAXN]; /*哈希*/

inline i64 ask (i64 l, i64 r) noexcept {
    return uha[r] - uha[l - 1] * ppow[r - l + 1]; /*大块的哈希值*/
}

inline i64 check (i64 x, i64 y) noexcept {
    i64 l = 1, r = rkuai, rp = 0,
        a = pos[x].first, b = pos[x].second,
        c = pos[y].first, d = pos[y].second;/*分别是哪一个块和往后移动了多少*/

    while (l <= r) {
        i64 mid = (l + r) >> 1;

        if (Ha[a].ask (b, b + mid - 1) == Ha[c].ask (d, d + mid - 1))
            rp = mid, l = mid + 1;
        else r = mid - 1;
    }

    return Ha[a].B[b + rp] > Ha[c].B[d + rp]; /*二分出块内第一个不一样的位置比较*/
}

int main() noexcept{
    read (k, m); scanf ("%s", (ch + 1));

    n = (1ll << k);
    for (i32 i = 1; i <= n; i++)
        ch[i + n] = ch[i]/*先拓展出两倍*/, to[i] = i/*变化之后的位置*/;

    for (i32 t = 1; t <= m % k; t++) {
        i64 cnt = 0;
        for (i32 i = 1; i <= n / 2; i++)
            rv[++cnt] = to[i], rv[++cnt] = to[i + n / 2];
        for (i32 i = 1; i <= n; i++)
            to[i] = rv[i];
    } /*直接暴力枚举变化之后对应的位置*/

    len = 1, rkuai = 1;
    /*len 块长 2^{m % k}，rkuai 块数 2^{k - m % k}*/
    for (i32 i = 1; i <= k - m % k; i++)
        len = len * 2;
    for (i32 i = 1; i <= m % k; i++)
        rkuai = rkuai * 2;

    ppow[0] = 1;
    for (i32 i = 1; i <= n * 2; i++) ppow[i] = ppow[i - 1] * p;
    /*哈希 base 预处理*/

    i64 blo = 0/*现在有多少个块*/;

    for (i32 i = 1; i <= n; i++) { /*先扒每一个块*/
        std::vector <i64> F; 
        for (i32 j = i; j <= i + rkuai - 1; j++)
            F.push_back (ch[to[j]] - 'a' + 1);

        for (i32 j = 0; j < rkuai; j++)
            F.push_back (F[j]); /*先拓展一倍*/
        F.insert (F.begin (), 0); /*从零开始存太恶心了，，*/

        Ha[++blo].insert (F); /*预处理块内哈希*/
        pos[blo] = {blo, 1}; uha[blo] = uha[blo - 1] * p + Ha[blo].hb;/*块之间的哈希值*/
        i += rkuai - 1; /*跳一个块*/
    }

    i64 cnt = 1/*现在对应原块的第几个*/,
        kr = 1/*现在应该是第几轮了*/, ans = 1 /*答案*/;

    ++blo;
    for (i32 i = n + 1; i <= n * 2; i++) {
        i64 v = (Ha[cnt].hb - Ha[cnt].B[kr] * ppow[rkuai - 1]) * p +
                            Ha[cnt].B[kr];
        /*将第一个位置放在最后一个来的哈希值*/
        Ha[cnt].hb = v;/*这个位置的总哈希值*/ uha[blo] = uha[blo - 1] * p + v;
        pos[blo] = {cnt, kr + 1};  /*对应最原始的哪一个块，往后移动了多少次*/

        i64 l = 1, r = len, pos = 0; 

        while (l <= r) {
            i64 mid = (l + r) >> 1;
            if (ask (ans, ans + mid - 1) ==
                ask (blo - len + 1, blo - len + 1 + mid - 1))
                    l = mid + 1, pos = mid;
            else r = mid - 1;
        } /*大块匹配，二分出第一个不一样的块*/

        pos++;
        if (pos <= len && check (ans + pos - 1, blo - len + 1 + pos - 1))
            ans = blo - len + 1;/*小块比较，找出第一个不一样的位置*/

        blo++; 
        if (cnt == len) cnt = 1, kr++;/*又轮到第一个块，那么该将 kr + 1 往后面丢了*/
        else cnt++;
    }

    for (i32 i = ans; i <= ans + len - 1; i++) {
        i64 v = pos[i].second, x = pos[i].first; 
        for (i32 j = 0; j < rkuai; j++)
            putchar (Ha[x].B[j + v] + 'a' - 1); /*输出块长个*/
    }
    return 0;
}

:::