题目：
翻译：
【已提交至洛谷CF1111D】
有一个恶棍的聚居地由几个排成一排的洞穴组成，每一个洞穴恰好住着一个恶棍。
每种聚居地的分配方案可以记作一个长为偶数的字符串，第(i)个字符代表第(i)个洞里的恶棍的类型。
如果一个聚居地的分配方案满足对于所有类型，该类型的所有恶棍都住在它的前一半或后一半，那么钢铁侠可以摧毁这个聚居地。
钢铁侠的助手贾维斯有不同寻常的能力。他可以交换任意两个洞里的野蛮人（即交换字符串中的任意两个字符）。并且，他可以交换任意次。
现在钢铁侠会问贾维斯(q)个问题。每个问题，他会给贾维斯两个数(x)和(y)。贾维斯要告诉钢铁侠，从当前的聚居地分配方案开始，他可以用他的能力创造多少种不同的方案，使得与原来住在第(x)个洞或第(y)个洞中的恶棍类型相同的所有恶棍都被分配到聚居地的同一半，同时满足钢铁侠可以摧毁这个聚居地。
如果某一个洞里的恶棍在两种方案中类型不同，则这两种方案是不同的。
输入
第一行包含一个字符串(s) ((2leq |s| leq 10^5))，表示初始的聚居地分配方案。字符串(s)包含小写和大写英文字母，且长度为偶数。
第二行包含一个整数(q)——询问的数量。
接下来的(q)行中的第(i)行包含两个整数(x_i)和(y_i) ((1leq x_i, y_i leq |s|))——第(i)个问题中给贾维斯的两个整数。
输出
对于每个问题输出可能的分配方案数模(10^9+7)。
分析：
前置技能
首先需要知道一个叫做“退背包”的东西，即给定(n)个物品，每个物品有体积(w[i])，求对于每一个(i(1leq i leq n))，当不存在第(i)个物品时，装满容量为(m)的背包的方案数。
暴力做法是对于每种(n-1)个物品的情况都(O(nm))做一次0-1背包，总复杂度(O(n^2m))，非常不优秀。“退背包”的做法是首先对全部(n)个物品做一遍背包，设(f[i])为装满容量为(i)的背包的方案数。如果当前第(i)个物品不存在，则从(f[k](v[i]leq ki leq m))中减去包含(i)的方案数。设此时答案为(g[k])，则：
于是对于每一种物品不存在的情况都可以用(O(m))的时间求出答案，总复杂度(O(nm))。模板题：洛谷4141
还需要知道可重集合的排列公式。即如果现在有(k)种元素，每种元素有(a_i)个，则该集合的排列计算公式是：
言归正传
回到这道题。先考虑算出总合法方案数（即(s_x=s_y)的情况）。首先统计出每种恶棍的出现次数(num[i])。设一种方案中前一半位置的恶棍种类组成集合(S)（即(sum_{iin S} num[i]=frac{n}{2})），则可以用背包DP算出(S)集合的方案数(f[frac{n}{2}])。然而，仅仅算出(S)集合的方案数是不够的，因为不同的排列被认为是不同的方案。根据上面的公式，前一半位置的排列方案数是：
然后就不幸地发现，这个方案数跟具体选出了哪些集合有关……gg
但是……如果把两半合在一起考虑呢？当一半的(S)集合确定，另一半的种类集合(S')也随之确定（设种类的全集为(U)，则(Scap S'=emptyset)且(Scup S'=U)）。两半的方案数相乘是当(S)确定时的最终方案数，即：
(U)是确定的，于是我们震惊地发现方案数与(S)无关……
所以，最终的答案就是：
其中(f[frac{n}{2}])是背包DP算出的(S)集合的方案数。
现在，我们算出了总的合法方案数，即解决了询问(s_x=s_y)（相当于没有限制）的情况。开始考虑(s_x eq s_y)的情况。设要求选到同一半的两种类型是(a)和(b)。此时不要想得太复杂（我刚写博客的时候都想得很复杂，写了很长一段然后删了233），这个限制只让上述(S)集合的方案数减少了。那一堆东西乘的不再是(f[frac{n}{2}])，而是不用(a)和(b)两种类型（相当于两种物品）填满(frac{n}{2})的方案数再乘(2)（因为(a)和(b)既可能在前一半，也可能在后一半），直接做两次退背包即可。注意到(|U|)很小，最大只有(52)，所以可以预处理每一对(a)和(b)的答案，每次需要(O(n))，总时间复杂度(O(n|U|^2+q))。虽然算下来有(2.7e8)，但是常数很小，加上Codeforces机器很快，所以可以过……
代码：
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cctype>
using namespace std;
namespace zyt
{
typedef long long ll;
const int N = 1e5 + 10, CH = 52, p = 1e9 + 7;
char str[N];
int f[N >> 1], g[N >> 1], h[N >> 1], cnt[CH][CH];
int num[CH], fac[N], finv[N];
int ctoi(const char c)
{
return isupper(c) ? c - 'A' + 26 : c - 'a';
}
inline int power(int a, int b)
{
int ans = 1;
while (b)
{
if (b & 1)
ans = (ll)ans * a % p;
a = (ll)a * a % p;
b >>= 1;
}
return ans;
}
inline int inv(const int a)
{
return power(a, p - 2);
}
inline void init()
{
fac[0] = 1;
for (int i = 1; i < N; i++)
fac[i] = (ll)fac[i - 1] * i % p;
finv[N - 1] = inv(fac[N - 1]);
for (int i = N - 1; i > 0; i--)
finv[i - 1] = (ll)finv[i] * i % p;
}
int work()
{
init();
scanf("%s", str);
int ans, len = strlen(str);
ans = (ll)fac[len >> 1] * fac[len >> 1] % p;
for (int i = 0; i < len; i++)
++num[ctoi(str[i])];
f[0] = 1;
for (int i = 0; i < CH; i++)
if (num[i])
{
ans = (ll)ans * finv[num[i]] % p;
for (int j = (len >> 1); j >= num[i]; j--)
f[j] = (f[j] + f[j - num[i]]) % p;
}
for (int i = 0; i < CH; i++)
if (num[i])
{
cnt[i][i] = f[len >> 1];
memcpy(g, f, sizeof(int[num[i]]));
for (int j = num[i]; j <= (len >> 1); j++)
g[j] = (f[j] - g[j - num[i]] + p) % p;
for (int j = i + 1; j < CH; j++)
if (num[j])
{
memcpy(h, g, sizeof(int[num[j]]));
for (int k = num[j]; k <= (len >> 1); k++)
h[k] = (g[k] - h[k - num[j]] + p) % p;
cnt[i][j] = cnt[j][i] = (ll)2LL * h[len >> 1] % p;
}
}
int q;
scanf("%d", &q);
while (q--)
{
int x, y;
scanf("%d%d", &x, &y);
printf("%lld
", (ll)ans * cnt[ctoi(str[x - 1])][ctoi(str[y - 1])] % p);
}
return 0;
}
}
int main()
{
return zyt::work();
}