[CF1111D]Destroy the Colony

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

题目大意： 有一个长度为$n(n\leqslant10^5,n=0\pmod2)$的字符串，字符集大小为$52$，有$q(q\leqslant10^5)$次询问，每次询问第$x,y$个字符在这个字符串的同一侧，并且所有相同字符在字符串的同一侧的方案数。

题解： 因为字符集大小只有$52$，所以本质不同的询问只有$52\times52$种，预处理。

发现若确定了左右各放那几种字符后方案数是一定的，为$\dfrac{\left(\dfrac n2!\right)^2}{\prod\limits_{i=1}^{52}cnt_i!}$，$cnt_i$表示字符$i$出现次数。只需要求出左边可以放的字符种类，乘上这个数就是答案。

考虑$DP$，若正常的做，不加入$x,y$两种字符，复杂度是$O(52^3\times n)$，不可以通过。发现最多只有两种字符不加入，可以退背包，就倒着做背包部分即可，复杂度$O(52^2\times n)$

卡点： 阶乘逆元算成了每个数的逆元

C++ Code：

#include <algorithm>

#include <cctype>

#include <cstdio>

#include <iostream>

#define maxn 100010

#define N 52

const int mod = 1e9 + 7;

inline void reduce(int &x) { x += x >> 31 & mod; }

std::string __s;

long long C;

int n, nn, q;

int fac[maxn], inv[maxn];

int s[maxn], cnt[N];

int f[maxn], g[maxn], ans[N][N];

int solve(int x, int y) {

	std::copy(f, f + nn + 1, g);

	for (int i = cnt[x]; i <= nn; ++i) reduce(g[i] -= g[i - cnt[x]]);

	for (int i = cnt[y]; i <= nn; ++i) reduce(g[i] -= g[i - cnt[y]]);

	return 2 * g[nn] % mod;

}

int main() {

	std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);

	std::cin >> __s; n = __s.length(), nn = n >> 1;

	for (int i = 0; i < n; ++i) {

		s[i + 1] = islower(__s[i]) ? __s[i] - 'a' : __s[i] - 'A' + 26;

		++cnt[s[i + 1]];

	}

	fac[0] = fac[1] = inv[0] = inv[1] = 1;

	for (int i = 2; i <= nn; ++i) {

		fac[i] = static_cast<long long> (fac[i - 1]) * i % mod;

		inv[i] = static_cast<long long> (mod - mod / i) * inv[mod % i] % mod;

	}

	for (int i = 2; i <= nn; ++i) inv[i] = static_cast<long long> (inv[i - 1]) * inv[i] % mod;

	C = static_cast<long long> (fac[nn]) * fac[nn] % mod;

	for (int i = 0; i < N; ++i) C = C * inv[cnt[i]] % mod;

	f[0] = 1;

	for (int i = 0; i < N; ++i) if (cnt[i])

		for (int j = nn; j >= cnt[i]; --j) reduce(f[j] += f[j - cnt[i]] - mod);

	for (int i = 0; i < N; ++i) if (cnt[i]) {

		for (int j = i + 1; j < N; ++j) if (cnt[j])

			ans[i][j] = ans[j][i] = solve(i, j);

		ans[i][i] = f[nn];

	}

	std::cin >> q;

	while (q --> 0) {

		static int x, y;

		std::cin >> x >> y; x = s[x], y = s[y];

		std::cout << C * ans[x][y] % mod << '\n';

	}

	return 0;

}