Counting Reorders
Calculate the number of ways you can reorder the characters of a string so that no two adjacent characters are the same.
For example, the answer for aabc is $6$, because the possible orders are abac, abca, acab, acba, baca, and caba.
$1 \leq n \leq 5000$
Tutorial
Consider the principle of inclusion-exclusion. Define $f\left(x\right)$ as the number of rearrangements such that for each $i$:
- if $x_i = 0$, there are no constraints.
- if $x_i = 1$, then $s_i = s_{i + 1}$ must hold.
Then we will realize that this operation is just dividing the whole string into several segments consisting of the same character. Moreover, the number of segments indicates how many indices $i$ satisfy $x_i = 1$.
Define $f_{i, j}$ as the number of rearrangements if we only use the first $i$ characters and resulting in exactly $j$ segments. When adding a new character, enumerate $k$, which indicates how many segments we will divided it into.
$$f_{i, j + k} \gets \binom{j + k}k \binom{cnt_i - 1}{k - 1} \cdot f_{i - 1, j}$$
Where $cnt_i$ represents the number of the $i$-th character. The term $\binom{j + k}k$ denotes the number of ways to insert the $k$ new segments among the existing $j$ segments. The term $\binom{cnt_i - 1}{k - 1}$ represents the number of ways to divide $cnt_i$ identical items into $k$ non-empty parts.
It seems that this method has a time complexity of $O\left(26 \cdot n^2\right)$, but in fact, it only costs $\sum\limits_{1 \leq i \leq 26}O\left(n \cdot cnt_i\right) = O\left(n^2\right)$.
Code
struct SNOWFLAKE {
SNOWFLAKE(int argc, char* argv[], int TEST_NUMBER) {
using lib::mint;
lib::mtg.init(1e9 + 7);
std::string s; std::cin >> s;
int n = s.size();
bsi cnt(26, 0);
for (auto i : s) ++cnt[i - 'a'];
stable_sort(cnt.rbegin(), cnt.rend());
while (cnt.back() == 0) cnt.pop_back();
std::vector<mint> f { 1 };
for (int i = 0; i < cnt.size(); ++i) {
std::vector<mint> g(f.size() + cnt[i]);
for (int j = 0; j < f.size(); ++j) {
for (int k = 1; k <= cnt[i]; ++k) {
g[j + k] += f[j] * mint::binom(j + k, k) * mint::binom(cnt[i] - 1, k - 1);
}
}
f = std::move(g);
}
mint tar;
for (int i = 0; i <= n; ++i) {
if (i % 2 == n % 2) tar += f[i];
else tar -= f[i];
}
std::cout << tar << "\n";
}
};