感觉是很裸的题。
考虑一个串 \(T\),它要交换多少次相邻字符才能等于 \(S\)。这是一个经典问题,设 \(p_i\) 为 \(T_i\) 在 \(T\) 的前缀 \([1, i]\) 中的出现次数,\(q_i\) 为 \(T_i\) 在 \(S\) 中第 \(p_i\) 次出现的位置,那么答案就是排列 \(q\) 的逆序对数。证明平凡故略。
由此也容易发现当 \(k > \frac{n(n - 1)}{2}\) 时能排列出所有能够排列出来的字符串。设字符 \(c\) 的出现次数为 \(cnt_c\),那么此时答案即为 \(\frac{(|S|!)}{cnt_{\text{A}}! cnt_{\text{B}}! cnt_{\text{C}!}}\)。
对于 \(k \le \frac{n(n - 1)}{2}\) 的情况,考虑 dp,\(f_{i, j, k, p}\) 表示当前填了 \(i\) 个 \(\text{A}\),\(j\) 个 \(\text{B}\),\(k\) 个 \(\text{C}\),用了 \(p\) 次交换的方案数。转移就考虑 \(T_{i + j + k}\) 填哪个字符即可,因为 \(i, j, k\) 都知道,所以此时 \(q_{i + j + k}\) 能被算出来。
时间复杂度 \(O(|S|^6)\),但是因为常数小所以跑得很快。
code
// Problem: E - Swap
// Contest: AtCoder - KEYENCE Programming Contest 2021 (AtCoder Beginner Contest 227)
// URL: https://atcoder.jp/contests/abc227/tasks/abc227_e
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef __int128 lll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 35;
int a[maxn], n, m;
ll f[maxn][maxn][maxn][500];
char s[maxn];
vector<int> vc[3];
void solve() {
scanf("%s%d", s + 1, &m);
n = strlen(s + 1);
for (int i = 1; i <= n; ++i) {
a[i] = (s[i] == 'K' ? 0 : (s[i] == 'E' ? 1 : 2));
vc[a[i]].pb(i);
}
if (m >= n * (n - 1) / 2) {
lll res = 1;
for (int i = 1; i <= n; ++i) {
res *= i;
}
for (int x = 0; x <= 2; ++x) {
for (int i = 1; i <= (int)vc[x].size(); ++i) {
res /= i;
}
}
printf("%lld\n", (ll)res);
return;
}
f[0][0][0][0] = 1;
for (int i = 0; i <= (int)vc[0].size(); ++i) {
for (int j = 0; j <= (int)vc[1].size(); ++j) {
for (int k = 0; k <= (int)vc[2].size(); ++k) {
for (int p = 0; p <= m; ++p) {
if (!i && !j && !k) {
continue;
}
if (i) {
int c = p;
for (int x = 0; x < i - 1; ++x) {
c -= (vc[0][x] > vc[0][i - 1]);
}
for (int x = 0; x < j; ++x) {
c -= (vc[1][x] > vc[0][i - 1]);
}
for (int x = 0; x < k; ++x) {
c -= (vc[2][x] > vc[0][i - 1]);
}
if (c >= 0) {
f[i][j][k][p] += f[i - 1][j][k][c];
}
}
if (j) {
int c = p;
for (int x = 0; x < i; ++x) {
c -= (vc[0][x] > vc[1][j - 1]);
}
for (int x = 0; x < j - 1; ++x) {
c -= (vc[1][x] > vc[1][j - 1]);
}
for (int x = 0; x < k; ++x) {
c -= (vc[2][x] > vc[1][j - 1]);
}
if (c >= 0) {
f[i][j][k][p] += f[i][j - 1][k][c];
}
}
if (k) {
int c = p;
for (int x = 0; x < i; ++x) {
c -= (vc[0][x] > vc[2][k - 1]);
}
for (int x = 0; x < j; ++x) {
c -= (vc[1][x] > vc[2][k - 1]);
}
for (int x = 0; x < k - 1; ++x) {
c -= (vc[2][x] > vc[2][k - 1]);
}
if (c >= 0) {
f[i][j][k][p] += f[i][j][k - 1][c];
}
}
}
}
}
}
ll ans = 0;
for (int i = 0; i <= m; ++i) {
ans += f[(int)vc[0].size()][(int)vc[1].size()][(int)vc[2].size()][i];
}
printf("%lld\n", ans);
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}
- Beginner AtCoder Contest Swap 227beginner atcoder contest swap contest programming beginner atcoder beginner atcoder contest 296 beginner atcoder contest 295 beginner atcoder contest abcde beginner atcoder contest 335 beginner atcoder contest 332 beginner atcoder contest 328 beginner atcoder contest 334 beginner atcoder contest 315