[ABC234] F - Reordering

Q. https://atcoder.jp/contests/abc234/tasks/abc234_f

1. 連続しない文字列をとるので、アルファベットaが何文字あるか、bが何文字あるか、という情報が大事になりそう。
2. どうやって何通りかを求めよう？

たとえば、
aaabb 5文字全部使う場合が何通りかを考える。
5文字を好きに並べ替えられるから、5!通り。

ところが、
a同士を入れ替えても種類数が増えないので、aの3文字 3!通りは重複。
b同士を入れ替えても種類数が増えないので、bの2文字 2!通りは重複。

なので、5! / 2!3! を求めればいい。

26種類のアルファベットで5000文字なので、DP[26][5000] をエスパーする。
3. DPの遷移をどうしよう。

aaabb
について。
aを0個、1個、2個、3個とる場合と、
bを0個、1個、2個とる場合、
の組み合わせになる。

貪欲にやると、26種類150個ずつの3900文字列だとして、150^26になって間に合わなそう。

また、4文字作る場合だけでも、
aaab
aabb
の2通りがあるので、これをユニークにせず管理するにはどうしよう。

aaab = 4! / 3!
aabb = 4! / 2!2!

1. 4!が重複部分だから、考察から除外する。
2. 分母の部分を固有に足し算できればまとめられそう。
DP[bを見てるとき][4文字] += 1 / 3! // aaab
DP[bを見てるとき][4文字] += 1 / 2!2! // aabb

これの遷移で構築すると、
1.) 初期値
DP[0][0] = 1 // 空文字の状態が1通り

2.) 遷移
DP['a' ~ 'z'][構成されている文字数0~N] = 重複している組み合わせ。分母の組み合わせの和。

3.) 解答
DP['z'][0 ~ N文字] * 文字数!
の総和になりそう。

4. 遷移の確認

Q. S=aaabb

DP[0][0]:1 // 空文字

DP[1][0]:1 // "" DP['a'][0] 今aを見ていて、これまでに0文字とった場合の重複数
DP[1][1]:1 // "a"
DP[1][2]:1/2! // "aa" aが2文字なので、1/2!
DP[1][3]:1/3! // "aaa" aが3文字なので、1/3!

DP[2][0]:1 // "" DP['b'][0] 今bを見ていて、これまでに0文字とった場合の重複数
DP[2][1]:2 // "a", "b" の重複数の総和。 1 + 1
DP[2][2]:2 // "aa", "ab", "bb" の重複数の総和。 1/2! + 1 + 1/2!
DP[2][3]:1/3! // "aaa", "aab", "abb" の重複数の総和 1/3! + 1/2! + 1/2!
DP[2][4]:1/3! // "aaab"
DP[2][5]:1/3! + 1/2! // "aaabb"

以降 c~z が出現しないので、新規に0文字採用するパターンを経て
DP['c'~'z'][0~5] = DP[2][0~5]

解答は、
ans += DP['z'][1] * 1!
ans += DP['z'][2] * 2!
ans += DP['z'][3] * 3!
ans += DP['z'][4] * 4!
ans += DP['z'][5] * 5!

ans = 33

実装

string S;
mint DP[27][5010];  // aが0~5000個
ll cnts[27];
mint perm[5010];
mint fperm[5010];

int main() {
 cincout();

 perm[0] = 1;
 perm[1] = 1;
 for (ll i = 2; i <= 5000; ++i) perm[i] = perm[i - 1] * i;

// 毎回modinv()するとTLE。事前にとっておく必要がある。
 fperm[0] = 1;
 fperm[1] = 1;
 for (ll i = 2; i <= 5000; ++i) fperm[i] = fperm[i - 1] * modinv(i, MOD);

 cin >> S;
 ll N = S.size();
 // aの数
 rep(i, N) { ++cnts[S[i] - 'a']; }

 rep(i, 27) {
   if (cnts[i] == N) {
     cout << N << endl;
     return 0;
   }
 }

 // DPに割る数を足す？
 DP[0][0] = 1;
 rep(i, 26) {
   for (ll j = 0; j <= cnts[i]; ++j) {  // 5000
     for (ll k = j; k <= N; ++k) {      // 5000
       if (DP[i][k - j] == 0) break;
       DP[i + 1][k] += DP[i][k - j] * fperm[j];
     }
   }
 }

 mint ans = 0;
 for (ll j = 1; j <= N; ++j) {
   ans += DP[26][j] * perm[j];
 }
 cout << ans << endl;
}

https://atcoder.jp/contests/abc234/submissions/28425947