三个字符串可还行
T1.字符串还原
我一开始读错题了，以为是要不断拆分，回头一看发现只用拆依次，这不就枚举断点，然后用\(hash\)判断不就行了吗。不过这样你会得到80分，原因是不同的断点可能出来的是同一个字符串，这只能算一种情况。
代码
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#define sandom signed
#include <bits/stdc++.h>
#define re register int
#define rep(i, a, b) for (re (i) = (a); (i) <= (b); ++(i))
using namespace std;
typedef unsigned long long ull; const int Z = 2e6 + 10; const ull B = 131;
int n, m, ans;
char s[Z];
ull ba[Z], has[Z], tot;
void init_hash()
{
ba[0] = 1;
rep(i, 1, n) ba[i] = ba[i - 1] * B;
rep(i, 1, n) has[i] = has[i - 1] * B + s[i] - 'A' + 1;
}
ull get(int l, int r) { return has[r] - has[l - 1] * ba[r - l + 1]; }
int solve()
{
rep(i, 1, n)//枚举插入位置
{
if (i < m && get(1, i - 1) * ba[m - i] + get(i + 1, m) == get(m + 1, n))
{
if (ans && tot != get(m + 1, n)) return 0;
ans = i, tot = get(m + 1, n);
}
if (i > m && get(1, m - 1) == get(m, i - 1) * ba[n - i] + get(i + 1, n))
{
if (ans && tot != get(1, m - 1)) return 0;
ans = i, tot = get(1, m - 1);
}
if (i == m && get(1, m - 1) == get(m + 1, n))
{
if (ans && tot != get(1, m - 1)) return 0;
ans = i, tot = get(1, m - 1);
}
}
if (ans) return ans;
else return -1;
}
inline void out(int l, int r) { rep(i, l, r) putchar(s[i]); }
sandom main()
{
cin >> n; m = n + 1 >> 1;
scanf("%s", s + 1);
init_hash();
int flag = solve();
if (flag == -1) puts("NOT POSSIBLE");//无解
else if (flag == 0) puts("NOT UNIQUE");//多解
else //唯一解
{
if (ans <= m) out(m + 1, n);
else out(1, m - 1);
}
return 0;
}
T2.数环
思想：先考虑链上的情况，把原数列处理成前缀和，可以发现每次操作相当于交换两个相邻的前缀和，即操作\(i\)这个位置，就是交换\(i-1、i\)两个位置的前缀和。那么问题就转化为交换两个相邻的元素，使得序列单调不减，且所有前缀和均非负，这个显然就是逆序对数了。至于环上的，我并不会。
T3.所有可能
你多校怎么这么爱考\(SA\)啊，考了三天，三天都有后缀数组或后缀自动机。
T4.字符串生成
\(dp\)式子基本上大部分人都一眼切了，但是实现不好搞，因为非线性，所以这个题除了各种千奇百怪做法。有使用科技的生成函数、差分线性递推、高斯消元……；字符串部分又分为了kmp、AC自动机。因为我不会\(kmp\)，所以打的魔改版AC自动机。发现停止的时候实际上就是拼接的字符串的后缀与原串相同。定义\(dp[i]\)表示存在前\(i\)个字母与原串相同的期望次数。转移为\(dp[i]=\frac{1}{2}dp[i+1]+\frac{1}{2}dp[f_{i+1}]+1\)，含义就是分为两种情况，一种是与原串相同，那么相同的长度加1；一种是不相同，那么要重新计算最大后缀匹配。我这里的\(f_i\)与\(nxt_i\)或失配指针类似，但有所不同，这也是我这种做法复杂度的关键。\(f_i\)表示前\(i-1\)个字符与原串相同，而第\(i\)个不同的最大后缀匹配，这玩意魔改一下AC自动机可以\(O(n)\)处理。因为我昨天刚做了游走（高斯消元+概率dp），所以直接整上去了，但是时间复杂度很废物，是\(O(n^3)\)；但又因为今天早上\(Sakura\)同志告诉我“分手是祝愿”这个题可以用差分来避免高斯消元，我得到了灵感，我通过给每一个式子乘上一个特定的\(2^i\)的系数，来把\(dp[i+1]\)这一项的转移消掉，最终得到了转移式\(2^{n-i-1}dp[i]=\sum\limits_{j=i+1}^n2^{n-j-1}dp[f_j]+2^{n-i}-1\)，可以发现这些转移只跟下标在\(f\)数组中出现过的未知元有关，说明原式中很多转移是无效的，那么我们可以把\(f\)数组离散化一下，把大小记为\(m\)，只对这\(m\)个未知元进行高斯消元，因为此时其他的系数都是0，完全没必要考虑。复杂度就是\(O(m^3)\)，怎么保证这个\(m\)的范围——根据对拍，在随机数据下\(m\)稳定在\(log_2n\)，我尝试了几种特殊构造，发现\(m\)反而更小了，原因就是我的\(f\)不是普通的\(nxt\)数组，而是对于每一个\(f_i\)，都有一个位置与原串不同，并且\(f_i\)之间的不同的位置也不同，所以很有可能\(m\)的级别就是\(log_2n\)的。不过还是希望有大佬可以证明——
代码
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#define sandom signed
#include <bits/stdc++.h>
#define re register int
#define int long long
#define rep(i, a, b) for (re (i) = (a); (i) <= (b); ++(i))
#define dwn(i, a, b) for (re (i) = (a); (i) >= (b); --(i))
using namespace std;
const int Z = 1e6 + 100; const int M = 5050; const int mod = 1e9 + 7; typedef long long ll;
inline int qpow(int a, int b, int c) { int res = 1; while (b) { if (b & 1) res = res * a % c; a = a * a % c; b >>= 1; } return res; }
int n, m, ans;
char s[Z];
int f[Z];
struct ACTrie
{
int kid[2];
int fail, len;
}; ACTrie ac[Z];
int tot, root;
int insert(int t)
{
ac[root].kid[t] = ++tot;
ac[tot].len = ac[root].len + 1;
if (!root) ac[tot].fail = 0, ac[root].kid[t ^ 1] = 0;
else ac[tot].fail = ac[ac[root].fail].kid[t],
ac[root].kid[t ^ 1] = ac[ac[root].fail].kid[t ^ 1];
int tmp = root;
root = tot;
return ac[ac[tmp].kid[t ^ 1]].len;
}
int a[M][M], inv2 = 500000004;
void Gauss(int n)
{
rep(k, 1, n)
{
int now = k;
rep(i, k + 1, n) if (abs(a[i][k]) > abs(a[now][k])) now = i;
swap(a[now], a[k]);
if (a[k][k] == 0) continue;
int tmp = qpow(a[k][k], mod - 2, mod);
dwn(j, n + 1, k) (a[k][j] *= tmp) %= mod;
rep(i, 1, n) if (i != k) dwn(j, n + 1, k) (a[i][j] -= a[i][k] * a[k][j]) %= mod;
}
}
int ls[Z], bow[Z];
void discret()
{
rep(i, 1, n) ls[i] = f[i];
sort(ls + 1, ls + 1 + n);
m = unique(ls + 1, ls + 1 + n) - ls - 1;
rep(i, 1, n) f[i] = lower_bound(ls + 1, ls + 1 + m, f[i]) - ls;
}
void solve()
{
bow[0] = 1;
rep(i, 1, n) bow[i] = (bow[i - 1] << 1) % mod;
rep(i, 1, m)
{
a[i][i] = bow[n - ls[i] - 1];
a[i][m + 1] = bow[n - ls[i]] - 1;
rep(j, ls[i] + 1, n - 1) (a[i][f[j]] -= bow[n - j - 1]) %= mod;
(a[i][f[n]] -= inv2) %= mod;
}
}
sandom main()
{
scanf("%s", s + 1); n = strlen(s + 1);
rep(i, 1, n) f[i] = insert(s[i] - '0');
discret();
solve();
Gauss(m);
cout << (a[1][m + 1] + mod) % mod << endl;
return 0;
}