Enough Already

宝宝题。

发现段数很少，据此 dp。记

f_{c,k}

表示只用前

c

种字符排列字符串得到恰好

k

个段的方案数。考虑字符

c+1

怎么插入，发现插入在原来的两段之间，对总段数贡献

1

，插在原来的一段内部会断裂一个段，贡献

2

。枚举插在内部的有

a

个位置，插在原来的段之间的有

b

个位置，再记

s

表示前

c

种字符总长度，

\text{cnt}_c

表示字符

c

个数，转移简单：

f_{c,k}\binom{s-k}{a}\binom{k+1}{b}\binom{\text{cnt}_{c+1}-1}{a+b-1}\to f_{c+1,k+2a+b}.

做完了。枚举

a,b

两维

O(m^2)

，时间复杂度

O(m^3\Sigma)

，其中

m

表示原串段数。

CPP

#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;
}

文章操作

相关推荐

评论

Enough Already