2018 Petrozavodsk Winter Camp, Yandex Cup 题目链接：gym102155F Shuffle
题目大意：
设字符串 s = s 1 s 2 ⋯ s n s=s_1s_2\cdots s_n s=s1s2⋯sn（ n n n 为偶数），定义操作：
shuffle ( s ) = s 1 s 3 ⋯ n − 1 s 2 s 4 ⋯ s n \text{shuffle}(s)=s_1s_3\cdots_{n-1}s_2s_4\cdots s_n shuffle(s)=s1s3⋯n−1s2s4⋯sn
给字符串 s s s 和 t t t ，问最少经过多少次 shuffle \text{shuffle} shuffle 后 s s s 变成了 t t t。
解题思路：
设：
s = a a b b c c d b a e t = a a b d c c b b a e \begin{aligned} s&=aabbccdbae\cr t&=aabdccbbae \end{aligned} st=aabbccdbae=aabdccbbae
首先把 shuffle \text{shuffle} shuffle 分解成几个不同的轮换，例如：
( 1 2 3 4 5 6 7 8 9 10 1 3 5 7 9 2 4 6 8 10 ) = ( 1 ) ( 2 3 5 9 8 6 ) ( 4 7 ) ( 10 ) \binom{1\ 2\ 3\ 4\ 5\ 6\ 7\ 8\ 9\ 10}{1\ 3\ 5\ 7\ 9\ 2\ 4\ 6\ 8\ 10}=(1)(2\ 3\ 5\ 9\ 8\ 6)(4\ 7)(10) (1 3 5 7 9 2 4 6 8 101 2 3 4 5 6 7 8 9 10)=(1)(2 3 5 9 8 6)(4 7)(10)
对于每个循环节，我们取出对应的 s s s 和 t t t 的子串：
( a a ) ( a b c a b c a b c a b c ) ( b d d b ) ( e e ) \binom{a}{a}\binom{abcabc}{abcabc}\binom{bd}{db}\binom{e}{e} (aa)(abcabcabcabc)(dbbd)(ee)
将 s s s 复制一遍得到 s s ss ss，我们可以通过 KMP 算法求出 t t t 在 s s ss ss 中第一次出现的位置 x i x_i xi 和 s s s 在 s s ss ss 中除了初位置之外第一次出现的位置 y i y_i yi（ y i y_i yi 也是 s s s 的最短循环节长度）。可知：
a n s m o d x i ≡ y i ans \bmod x_i\equiv y_i ansmodxi≡yi
通过 EXCRT 合并即可得到答案。
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 2e6 + 50; string s, t; int n, b[N]; int vis[N]; int nxt[N]; vector<int> x, y; inline ll mul(ll x, ll y, ll P) { return (x * y - (ll)((long double)x / P * y) * P + P) % P; //return 1LL * x * y % P; } ll exgcd(ll a, ll b, ll &x, ll &y) { if (b == 0) { x = 1; y = 0; return a; } ll gcd = exgcd(b, a % b, x, y); ll t = x; x = y; y = t - a / b * y; return gcd; } ll excrt(vector<int> &ai, vector<int> &bi) { int n = (int)ai.size(); ll x, y; ll M = bi[0], ans = ai[0]; for (int i = 1; i < n; i++) { ll a = M, b = bi[i], c = (ai[i] - ans % b + b) % b; ll gcd = exgcd(a, b, x, y), bg = b / gcd; if (c % gcd) return -1; x = mul(x, c / gcd, bg); ans += x * M; M *= bg; ans = (ans % M + M) % M; } return ans; } int main() { cin >> s >> t; n = (int)s.length(); for (int i = 1; i <= n; i++) { if (i <= n / 2) b[i] = 2 * i - 1; else b[i] = 2 * (i - n / 2); } nxt[0] = -1; for (int i = 1; i <= n; i++) if (!vis[i]) { int cnt = 0, tmp = i; string ns, nt; while (!vis[tmp]) { vis[tmp] = 1; cnt++; tmp = b[tmp]; ns += s[tmp - 1]; nt += t[tmp - 1]; } ns += ns; vector<int> yy; int lent = (int)nt.length(); for (int ii = 2, j = 0; ii <= lent; ii++) { while(~j && nt[j+1-1] != nt[ii-1]) j = nxt[j]; nxt[ii] = ++j; } int lens = (int)ns.length(), pos = 0, flag = 0; for (int ii = 1, j = 0; ii <= lens; ii++) { while (~j && nt[j+1-1] != ns[ii-1]) j = nxt[j]; j++; if (j == lent) { pos = ii-lent+1; flag = 1; break; } } if (!flag) { puts("-1"); return 0; } int looplen = lent - nxt[lent]; if (cnt % looplen == 0) cnt = looplen; x.push_back(cnt); y.push_back(pos - 1); } printf("%lld\n", excrt(y, x)); return 0; }