[Solution] CF1111D
KaguyaH
·
·
题解
有一偶数长度字符串 s，q 次询问，每次询问给两位置 x, y，求满足下列条件的 s 的排列 p 的方案数。
- 对于任意字符，要么集中在 p 前半段，要么集中在 p 后半段；
-
两种排列方案 p, q 不同，当且仅当 \exists 1 \leq i \le |s| 满足 p_i \neq q_i。
---
记字符集为 $\Sigma$，有 $|\Sigma| = 52$。比较显然地，本质不同的询问仅有至多 $|\Sigma|^2$ 种。
如果已经钦定各字符在哪一段，设 $c_x$ 为字符 $x$ 的出现次数，则方案数为
$$C = (\frac n 2)!^2 \prod_{x} c_x!^{-1}.$$
考虑钦定 $s_x, s_y$ 均在前半段，设钦定方案数为 $g$，则答案为 $2Cg$。
考虑求出 $g$。
定义 $f_x$ 表示选择一些字符 $\Sigma'$，使 $\sum_{i \in \Sigma'} c_i = x$ 的方案数。
$\forall x, y \in \Sigma$，利用支持删除操作的背包，在 $f$ 中依次删去 $x, y$，得到 $f'$，则 $g_{x, y} = f'_{\frac {|s|} 2 - c_x - c_y}$。
注意特殊处理 $x = y$ 的情况。
时间复杂度 $\mathcal O(|s|(|\Sigma|^2 + \log|s|))$，空间复杂度 $\mathcal O(|\Sigma|^2 + |s|)$，可过。
---
```cpp
# include <ciso646>
# include <cstdio>
# include <cstring>
# define forletter(i) for (char i('a'); i not_eq 'Z' + 1; i == 'z' ? (i = 'A') : ++i)
namespace Main {
typedef unsigned int uint;
typedef short unsigned int hu;
static inline const uint qpow(uint a, uint n, const uint mod) {
uint r(1);
while (n) {
if (n bitand 1) r = 1ull * r * a % mod;
a = 1ull * a * a % mod, n >>= 1;
}
return r;
}
static inline const uint invp(const uint x, const uint p) { return qpow(x, p - 2, p); }
static const uint S(1e5);
static const uint P(1e9 + 7);
static uint fact[S + 1]{ 1 }, ifact[S + 1]{ 1 };
static char s[S + 2];
static uint n, q;
static uint c[128];
static uint f[S + 1]{ 1 };
static uint g[128][128];
static uint bc;
static inline const void init() {
n = strlen(s + 1);
for (register uint i(1); i <= n; ++i) ifact[i] = invp(fact[i] = 1ull * fact[i - 1] * i % P, P);
f[0] = 1;
for (register uint i(1); i <= n; ++i) ++c[s[i]];
forletter(i) if (c[i]) for (register uint j(n); j >= c[i]; --j) f[j] = (f[j] + f[j - c[i]]) % P;
bc = 1ull * fact[n / 2] * fact[n / 2] % P;
forletter(i) bc = 1ull * bc * ifact[c[i]] % P;
}
static inline const void solve(const char a, const char b) {
if (!c[a] or !c[b]) return;
if (a == b) {
if (c[a] > n / 2) return (const void)(g[a][a] = 0);
static uint h[S + 1]; for (register uint i(0); i <= n; ++i) h[i] = f[i];
for (register uint i(c[a]); i <= n; ++i) h[i] = (h[i] + P - h[i - c[a]]) % P;
return (const void)(g[a][a] = 1ull * h[n / 2 - c[a]] * bc * 2 % P);
}
if (c[a] + c[b] > n / 2) return (const void)(g[a][b] = 0);
static uint h[S + 1]; for (register uint i(0); i <= n; ++i) h[i] = f[i];
for (register uint i(c[a]); i <= n; ++i) h[i] = (h[i] + P - h[i - c[a]]) % P;
for (register uint i(c[b]); i <= n; ++i) h[i] = (h[i] + P - h[i - c[b]]) % P;
g[a][b] = 1ull * h[n / 2 - c[a] - c[b]] * bc * 2 % P;
}
static inline const void main() {
scanf("%s", s + 1), init();
forletter(i) forletter(j) solve(i, j);
scanf("%u", &q);
for (register uint i(0); i < q; ++i) { static uint x, y; scanf("%u%u", &x, &y), printf("%u\n", g[s[x]][s[y]]); }
}
}
signed int main() { Main::main(); return 0; }
```