original link - http://codeforces.com/contest/1111/problem/D
题意:
给出一个字符串,每次选择两个位置的字符,问有多少种字符串满足:
- 可以由原字符串任意次交换两个字符后得到;
- 选择的字符(两个或者一个)同时只出现在一边;
- 其他字符只出现一边。
解析:
假设选择的字符在左边(右边的情况相同,最后乘二即可),考虑两个字符不同的情况。
那么就是在不选择a的背包里面,退掉b的siz,最后的dp[len/2−siz[a]−siz[b]]就是可行的方案。
每个方案现在还只是组合,变为排列的话,发现每种组合固定有siz[i]!2len!2len!种排序。
代码:
/*
* Author : Jk_Chen
* Date : 2019-09-16-15.03.32
*/
#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define rep(i,a,b) for(int i=(int)(a);i<=(int)(b);i++)
#define per(i,a,b) for(int i=(int)(a);i>=(int)(b);i--)
#define mmm(a,b) memset(a,b,sizeof(a))
#define pb push_back
#define pill pair<int, int>
#define fi first
#define se second
#define debug(x) cerr<<#x<<" = "<<x<<'\n';
const LL mod=1e9+7;
const int maxn=1e5+9;
LL rd(){ LL ans=0; char last=' ',ch=getchar();
while(!(ch>='0' && ch<='9'))last=ch,ch=getchar();
while(ch>='0' && ch<='9')ans=ans*10+ch-'0',ch=getchar();
if(last=='-')ans=-ans; return ans;
}
/*_________________________________________________________begin*/
LL Pow(LL a,LL b,LL mod){
LL res=1;
while(b>0){
if(b&1)res=res*a%mod;
a=a*a%mod;
b>>=1;
}
return res;
}
LL fac[maxn],ifac[maxn];
/*_________________________________________________________Pow*/
char x[maxn];
int ct[100];
int id(char c){
if(islower(c))return c-'a';
return c-'A'+26;
}
LL dp[52][maxn/2];
LL ans[52][52];
LL tmp[maxn/2];
int main(){
fac[0]=1;
rep(i,1,maxn-1)fac[i]=fac[i-1]*i%mod;
ifac[maxn-1]=Pow(fac[maxn-1],mod-2,mod);
per(i,maxn-2,0)ifac[i]=ifac[i+1]*(i+1)%mod;
gets(x+1);
int len=strlen(x+1);
rep(i,1,len){
ct[id(x[i])]++;
}
rep(i,0,51)dp[i][0]=1;
rep(i,0,51){
if(!ct[i])continue;
rep(j,0,51){
if(i==j||!ct[j])continue;
per(k,len/2,ct[i]){
dp[j][k]=(dp[j][k]+dp[j][k-ct[i]])%mod;
}
}
}
rep(i,0,51)
if(ct[i]&&ct[i]<=len/2)
ans[i][i]=dp[i][len/2-ct[i]];
rep(i,0,50){
if(ct[i]==0)continue;
rep(j,i+1,51){
if(ct[j]==0)continue;
if(ct[i]+ct[j]>len/2)continue;
if(i==2&&j==3){
i=2;
}
rep(k,0,len/2)tmp[k]=dp[i][k];
rep(k,ct[j],len/2){
tmp[k]=(tmp[k]+mod-tmp[k-ct[j]])%mod;
}
ans[i][j]=tmp[len/2-ct[i]-ct[j]];
}
}
int t=rd();
LL mul=2ll*fac[len/2]*fac[len/2]%mod;
rep(i,0,51){
mul=mul*ifac[ct[i]]%mod;
}
while(t--){
int l=rd(),r=rd();
l=id(x[l]),r=id(x[r]);
if(l>r)swap(l,r);
printf("%lld\n",ans[l][r]*mul%mod);
}
return 0;
}