CF2172H - Shuffling Cards with Problem Solver 68!

Aru loves playing card games (Poker, Texas hold 'em, Balatro, etc.) and she has perfected the art of shuffling cards, especially the riffle shuffle. She is playing with Mutsuki now, and it's her turn to shuffle the cards!

However, Mutsuki knows that Aru is too perfect with her shuffling game. In fact, given a deck with an even number of cards, Aru always performs a perfect riffle: she cuts the deck evenly and interleaves the two halves. Formally, if the deck is represented by a string \(s\) of length \(n\), where \(s_i\) is the \(i\)-th card from the top, one riffle produces the deck

\[s^\prime = s_1 + s_{n/2 + 1} + s_2 + s_{n/2 + 2} + \ldots + s_{n/2} + s_{n}. \]

Mutsuki also knows that when handed a deck of cards, Aru will riffle it exactly \(t\) times.

Mutsuki currently holds a deck of \(2^k\) cards, represented by a string \(d\). Before giving the deck to Aru, Mutsuki can choose to cut the deck, by moving some number of cards from the top to the bottom of the deck. Formally, she can choose any \(m\) from \(0\) to \(2^k - 1\), and produce the deck

\[d^\prime = d_{m + 1} + d_{m + 2} + \ldots + d_{2^k} + d_1 + d_2 + \ldots + d_m. \]

Among all \(2^k\) possible cuts, Mutsuki wants to choose the one that results in the lexicographically smallest deck after Aru riffles it \(t\) times. Can you figure this out for her?

Input

The first line contains two integers \(k\) and \(t\), representing the size parameter of the deck, and the number of times Aru will riffle the deck, respectively.

The second line contains a string \(d\) of \(2^k\) lowercase characters, representing the original deck of cards that Mutsuki has.

• \(1 \le k \le 18\)
• \(0 \le t \le 10^9\)

Output

Print a string in one line, representing the lexicographically smallest deck of cards that Mutsuki can produce, by first cutting the deck and letting Aru riffle it \(t\) times.

---

考虑外洗法的洗牌规律，不妨设牌从上到下为 \(s[0 \sim n - 1]\)，不难发现一次洗牌相当于在模 \(n - 1\) 意义下乘二，而 \(ord_{2^k - 1}(2) = k\)，也即阶为 \(k\)，故题面的 \(t\) 可以视为 \(k\) 的大小。

考虑预处理出每张牌的映射，我们可以知道对于任意一个位移的字符串是什么，所以可以对每个位移做排序。而做排序也很简单，只用二分出每一个字符串相等的部分，找到一下个恰好满足条件的字符串即可。

时间复杂度 \(O(n\log^2{n})\) 或 \(O(n\log{n})\)。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define i128 __int128
#define ld long double
#define PII pair<ll, ll>
#define PPI pair<ll, PII>
#define clr(f, n) memset(f, 0, sizeof(int) * (n))
#define cpy(f, g, n) memcpy(f, g, sizeof(int) * (n))
#define rev(f, n) reverse(f, f + (n))
const int N = 2e5 + 10, mod = 998244353, INF = 1e9;
const ll B = 331;void solve() {int k, t, n;cin >> k >> t, n = 1 << k, t %= k;string s; cin >> s;vector<int> p(n);vector<vector<ll>> st(k, vector<ll>(n));vector<ll> base = {B}; base.resize(k);iota(p.begin(), p.end(), 0);while (t -- ) for (int i = 1; i < n - 1; i ++ ) p[i] = (p[i] >> 1) | ((p[i] & 1) << (k - 1));for (int i = 1; i < k; i ++ ) base[i] = base[i - 1] * base[i - 1];for (int i = 0; i < k; i ++ ) {for (int j = 0; j < n; j ++ ) {if (!i) st[i][j] = s[j];else st[i][j] = st[i - 1][j] * base[i - 1] + st[i - 1][(j + p[1 << (i - 1)]) % n];}}auto cmp = [&](int x, int y) {for (int i = k - 1; i >= 0; i -- ) {if (st[i][x] == st[i][y]) {x = (x + p[1 << i]) % n;y = (y + p[1 << i]) % n;}}return s[x] < s[y];};int ans = 0;for (int i = 1; i < n; i ++ ) if (cmp(i, ans)) ans = i;for (int i = 0; i < n; i ++ ) cout << s[(p[i] + ans) % n];
}int main() {ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int T = 1;// cin >> T;while (T -- ) solve();return 0;
}