题意：

这个题目真的是最近遇到的最难读。

有一个长度n的字符串，每一位字符都代表的是该种种类的敌人。

现在如果一个序列合法的话，就是同一种种类的敌人都在字符串的左半边或者右半边。

现在有q次询问，现在问你将 s[x] 和 s[y] 的敌人都放在同一边的合法方案数是多少。

题解：

首先如果划分组之后，那么答案就是，m! * m! * 2/ (c1! * c2! * c3! .... ) 

然后对于每一组来说就是 这个值是一定的。

然后就是需要求这个分组方案数。

对于分组方案数，可以通过背包来求这个方案数是多少。

但是如果枚举每个同类的字符，那么最后的复杂度是52 * 52 * 52 * n。

所以可以将总方案数先算出来，然后再将x，y的方案数，从里面删除，删除之后，不含x,y的方案数，相当于含了x,y的方案数。 这个复杂度是52*52*n。

 

代码：

/*code by: zstu wxktime: 2019/02/07*/#include
      
       using namespace std;#define Fopen freopen("_in.txt","r",stdin); freopen("_out.txt","w",stdout);#define LL long long#define ULL unsigned LL#define fi first#define se second#define pb push_back#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1#define lch(x) tr[x].son[0]#define rch(x) tr[x].son[1]#define max3(a,b,c) max(a,max(b,c))#define min3(a,b,c) min(a,min(b,c))typedef pair
       
         pll;const int inf = 0x3f3f3f3f;const int _inf = 0xc0c0c0c0;const LL INF = 0x3f3f3f3f3f3f3f3f;const LL _INF = 0xc0c0c0c0c0c0c0c0;const LL mod =  (int)1e9+7;const int N = 1e5 + 100;int cnt[N];char s[N];LL ans[60][60];int F[N], Finv[N], inv[N];/// F是阶层 Finv是逆元的阶层void init(){    inv[1] = 1;    for(int i = 2; i < N; i++)        inv[i] = (mod - mod/i) * 1ll * inv[mod % i] % mod;    F[0] = Finv[0] = 1;    for(int i = 1; i < N; i++){        F[i] = F[i-1] * 1ll * i % mod;        Finv[i] = Finv[i-1] * 1ll * inv[i] % mod;    }}int comb(int n, int m){ /// C(n,m)    if(m < 0 || m > n) return 0;    return F[n] * 1ll * Finv[n-m] % mod * Finv[m] % mod;}int id(char ch){    if(islower(ch)) return ch - 'a' + 1;    return ch - 'A' + 27;}int dp[N], tp[N];void Ac(){    int n = strlen(s+1);    int m = n / 2;    for(int i = 1; i <= n; ++i)        ++cnt[id(s[i])];    dp[0] = 1;    for(int i = 1; i <= 52; ++i){        if(cnt[i]){            for(int j = m; j >= cnt[i]; --j)                dp[j] = (dp[j] + dp[j-cnt[i]]) % mod;        }    }    for(int i = 0; i <= m; ++i)        tp[i] = dp[i];    for(int i = 1; i <= 52; ++i){        if(cnt[i] && cnt[i] <= m){            for(int j = cnt[i]; j <= m; ++j){                dp[j] = (dp[j] - dp[j-cnt[i]] + mod) % mod;            }            ans[i][i] = dp[m];            for(int j = 1; j <= 52; ++j){                if(cnt[j] && cnt[j] <= m && j != i){                    for(int k = cnt[j]; k <= m; ++k){                        dp[k] = (dp[k] - dp[k-cnt[j]] + mod)%mod;                    }                    ans[i][j] = dp[m];                    for(int k = m; k >= cnt[j]; --k){                        dp[k] = (dp[k] + dp[k-cnt[j]]) % mod;                    }                }            }            for(int j = m; j >= cnt[i]; --j)                dp[j] = tp[j];        }    }    LL zz = 2ll * F[m] * F[m] % mod;    for(int i = 1; i <= 52; ++i)        zz = (zz * Finv[cnt[i]]) % mod;    int q, x, y;    scanf("%d", &q);    while(q--){        scanf("%d%d", &x, &y);        printf("%I64d\n", zz * ans[id(s[x])][id(s[y])] % mod);    }    return ;}int main(){    init();    while(~scanf("%s", s+1)){        Ac();    }    return 0;}