Enough Already

冷却心 · 2025-10-23 14:02:08 · 题解

宝宝题。

发现段数很少，据此 dp。记 f_{c,k} 表示只用前 c 种字符排列字符串得到恰好 k 个段的方案数。考虑字符 c+1 怎么插入，发现插入在原来的两段之间，对总段数贡献 1，插在原来的一段内部会断裂一个段，贡献 2。枚举插在内部的有 a 个位置，插在原来的段之间的有 b 个位置，再记 s 表示前 c 种字符总长度，\text{cnt}_c 表示字符 c 个数，转移简单：

做完了。枚举 a,b 两维 O(m^2)，时间复杂度 O(m^3\Sigma)，其中 m 表示原串段数。

#include <bits/stdc++.h>
#define LL long long
#define ull unsigned long long
#define uint unsigned int
using namespace std;
const int N = 2e6 + 10;
const int M = 110;
const ull MOD = 1000003;
ull Qpow(ull x, ull k, ull P) {
    ull res = 1, tmp = (x + P) % P;
    for (; k; k >>= 1, tmp = tmp * tmp % P) if (k & 1) res = res * tmp % P;
    return res;
}
int n, m, lim = 1e6; char S[N]; int cnt[30];
ull fact[N], inv[N], F[30][M];
ull C(int n, int m) { return (n < m ? 0 : fact[n] * inv[m] % MOD * inv[n - m] % MOD); }
int main() {
    ios::sync_with_stdio(false); cin.tie(0), cout.tie(0);
    fact[0] = 1;
    for (int i = 1; i <= lim; i ++) fact[i] = fact[i - 1] * i % MOD;
    inv[lim] = Qpow(fact[lim], MOD - 2, MOD);
    for (int i = lim - 1; i >= 0; i --) inv[i] = inv[i + 1] * (i + 1) % MOD;

    int _; cin >> _;
    for (int __ = 1; __ <= _; __ ++) {
        cin >> (S + 1); n = strlen(S + 1); m = 1;
        for (int i = 1; i < n; i ++) m += (S[i] != S[i + 1]);
        for (int i = 1; i <= n; i ++) cnt[S[i] - 'a' + 1] ++;
        bool flag = false; int len = 0;
        for (int i = 1; i <= 26; i ++) {
            if (!cnt[i]) { 
                for (int j = 0; j <= min(len, m); j ++) F[i][j] = F[i - 1][j]; 
                continue; 
            }
            if (!flag) { F[i][1] = 1; len = cnt[i]; flag = true; continue; }
            for (int j = 0; j <= min(len, m); j ++) 
                for (int a = 0; a <= min(m, cnt[i]); a ++) 
                    for (int b = 0; a + b <= cnt[i] && b <= m; b ++)
                        if (a + b > 0 && j + a * 2 + b <= m)
                            (F[i][j + a * 2 + b] += F[i - 1][j] * C(cnt[i] - 1, a + b - 1) % MOD * C(j + 1, b) % MOD * C(len - j, a) % MOD) %= MOD;
            len += cnt[i];
        }
        cout << "Case #" << __ << ": " << F[26][m] << "\n";
        for (int i = 1; i <= 26; i ++) for (int j = 0; j <= m; j ++) F[i][j] = 0;
        memset(cnt, 0, sizeof cnt);
    }
    return 0;
}