C. Constructive Problems Never Die
对于出现次数大于1的数字，用出现次数为0的数字填充。
剩下的数字一定两两互不相同，对这些数循环移位，最后进行判断即可。
#include<bits/stdc++.h>
#define pii pair<int, int>
#define fi first
#define se second
using namespace std;
const int MAXN = 1e5 + 5;
int n, num[MAXN], a[MAXN], res[MAXN];
vector<int> G[MAXN], vec;
priority_queue<pii> Q;
void Solve() {
cin >> n;
vec.clear();
while(!Q.empty()) Q.pop();
for(int i = 1; i <= n; i++) num[i] = 0, G[i].clear();
for(int i = 1; i <= n; i++) {
cin >> a[i];
num[ a[i] ]++;
G[ a[i] ].push_back(i);
}
int flag = 1;
for(int i = 1; i <= n; i++) Q.push({num[i], i});
for(int i = 1; i <= n; i++) {
if(num[i] == 0) {
pii x = Q.top(); Q.pop();
if(x.fi <= 1) { flag = 0; break; }
res[ G[x.se].back() ] = i;
G[x.se].pop_back();
x.fi--; Q.push(x);
} else {
vec.push_back(G[i][0]);
}
}
//for(auto i : vec) cout << i << " "; cout << "vec\n";
if(Q.top().fi >= 2) flag = 0;
int p = 1, sze = vec.size();
p %= sze;
for(auto i : vec) res[ vec[p] ] = a[i], p = (p + 1) % sze;
for(int i = 1; i <= n; i++) if(res[i] == a[i]) flag = 0;
if(flag) {
cout << "YES\n";
for(int i = 1; i <= n; i++) cout << res[i] << " ";
cout << "\n";
} else {
cout << "NO\n";
}
}
signed main()
{
//ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int T; cin >> T;
while(T--) Solve();
return 0;
}
I. Suffix Sort
考虑对所有后缀排序，直接用sort本身需要 \(O(nlogn)\)，我们考虑如何在 \(O(logn)\) 之内比较两个字符串的最小表示的大小。
只考虑最小表示法下字符为 \(ch\) 的出现位置，设对后缀 \([x...n]\) 和 \([y...n]\) 进行比较，出现位置分别为 \(posx_1, posx_2 ... posx_k\) 和 \(posy_1, posy_2 ... posy_k\)。
设只考虑字符 \(ch\) 的条件下，两个后缀中的前 \(k\) 个位置相同。其等价于
\[posx_1-x = posy_1-y \\ posx_{i}-posx_{i-1} = posy_{i}-posy_{i-1},i>1 \]直接二分第一个失配位置，朴素的时间复杂度大概为 \(O(26 \cdot logn)\)，会被卡。
想办法让二分边界逐渐减小，进行一些优化，时间复杂度大概为 \(O(26 + logn)\)。
复杂度 \(O(26nlog^2n)\) ，卡常。
#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 4e5 + 5;
const int MOD = 1e9 + 7;
const int BASE = 29;
int Min[MAXN][30], val[MAXN], sa[MAXN], rkA[30], rkB[30], vec[30], n;
long long h[30][MAXN], Pow[MAXN], Inv[MAXN];
string S;
vector<int> pos[30];
long long qpow(long long a, int p) {
long long res = 1;
while(p) {
if(p & 1) res = res * a % MOD;
a = a * a % MOD;
p >>= 1;
}
return res;
}
int Hash(int id, int l, int r) { return (h[id][r] - h[id][l - 1] + MOD) % MOD * Inv[l - 1] % MOD; }
bool cmp(int a, int b) {
int L = 1, R = n - max(a, b) + 1;
int *MinA = Min[a], *MinB = Min[b];
for(int i = 0; i < 26 && R > 1; ++i) {
if(MinA[i] - a >= R && MinB[i] - b >= R) break;
if(MinA[i] - a != MinB[i] - b) {
R = min(MinA[i] - a, MinB[i] - b);
break;
}
int vA = val[ MinA[i] ], vB = val[ MinB[i] ];
if( Hash(vA, a, a + R - 1) == Hash(vB, b, b + R - 1) ) continue;
int l = L, r = R;
while(l < r) {
int mid = l + r + 1 >> 1;
if( Hash(vA, a, a + mid - 1) == Hash(vB, b, b + mid - 1) ) l = mid;
else r = mid - 1;
}
if( Hash(vA, a, a + l - 1) == Hash(vB, b, b + l - 1) ) R = l;
}
if(max(a, b) + R > n) return a > b;
for(int i = 0; i < 26; ++i) rkA[i] = rkB[i] = 0;
for(int i = 0; i < 26; ++i) {
if(MinA[i] <= n) rkA[ val[ MinA[i] ] ] = i;
if(MinB[i] <= n) rkB[ val[ MinB[i] ] ] = i;
}
return rkA[ val[a + R] ] < rkB[ val[b + R] ];
}
signed main()
{
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> n >> S;
for(int i = 1; i <= n; ++i) val[i] = S[i - 1] - 'a';
Pow[0] = Inv[0] = 1; Inv[1] = qpow(BASE, MOD - 2);
for(int i = 1; i <= n; ++i) {
Pow[i] = Pow[i - 1] * BASE % MOD;
if(i > 1) Inv[i] = Inv[i - 1] * Inv[1] % MOD;
}
for(int i = 1; i <= n; ++i) {
for(int j = 0; j < 26; ++j) h[j][i] = h[j][i - 1];
h[ val[i] ][i] = (h[ val[i] ][i] + Pow[i]) % MOD;
pos[ val[i] ].push_back(i);
sa[i] = i;
}
for(int j = 0; j < 26; ++j) pos[j].push_back(n + 1);
for(int i = 1; i <= n; ++i) {
for(int j = 0; j < 26; ++j) vec[j] = *lower_bound(pos[j].begin(), pos[j].end(), i);
sort(vec, vec + 26);
for(int j = 0; j < 26; ++j) Min[i][j] = vec[j];
}
for(int i = 1; i <= n; ++i) sa[i] = i;
sort(sa + 1, sa + 1 + n, cmp);
for(int i = 1; i <= n; ++i) cout << sa[i] << " ";
return 0;
}
J. Melborp Elcissalc
设 \(f[i][j][k]\) 表示值取 \([0,i)\)， 填充了 \(j\) 个位置，goodness为 \(k\) 的前缀和数组数（原数组和前缀和数组一一对应）。
设当前选了 \(l\) 个值为 \(i\) 的数填充进前缀和数组，对于goodness的贡献（设为 \(cur\)）分为两种情况：
① \(i==0\) 时，贡献为 \(\C_{l+1}^{2}\)；① \(i>0\) 时，贡献为 \(\C_{l}^{2}\)。
有 \(f[i][j+l][k+cur] += f[i-1][j][k]*\C_{j+l}^{l}\)
初始化 \(f[0][0][0]=1\)，答案 \(f[k][n][t]\)
#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define int long long
#define pii pair<int, int>
#define fi first
#define se second
using namespace std;
const int MOD = 998244353;
int N, K, T, C[5005][5005], f[70][70][5005];
signed main()
{
//ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> N >> K >> T;
C[0][0] = 1;
for(int i = 1; i <= 5000; i++) {
C[i][0] = 1;
for(int j = 1; j <= i; j++) {
C[i][j] = C[i - 1][j] + C[i - 1][j - 1];
C[i][j] %= MOD;
}
}
f[0][0][0] = 1;
for(int i = 1; i <= K; i++) {
for(int j = 0; j <= N; j++) {
for(int k = 0; k <= T; k++) {
for(int l = 0; j + l <= N; l++) {
if(i == 1) {
if(k + C[l + 1][2] > T) break;
f[i][j + l][k + C[l + 1][2] ] += f[i - 1][j][k] * C[j + l][l] % MOD;
f[i][j + l][k + C[l + 1][2] ] %= MOD;
} else {
if(k + C[l][2] > T) break;
f[i][j + l][k + C[l][2] ] += f[i - 1][j][k] * C[j + l][l];
f[i][j + l][k + C[l][2] ] %= MOD;
}
}
}
}
}
cout << f[K][N][T];
return 0;
}