https://codeforces.com/contest/1111/problem/D
多重排列 + 反向01背包
题意:
给你一个字符串(n<=1e5,n为偶数),有q个询问,每次询问两个位置x和y,问将和x,y相同的所有字符移到前半段或者后半段,并且剩下的所有字符都要在同一半段的方案数,字符是大写小写字母
题解:
- 首先不考虑x和y位置,假设前半段的排列数为((n/2)!/(cnt[x_1]!*...*cnt[x_n]!)),后半段的排列为((n/2)!/(cnt[y_1]!*...*cnt[y_n]!)),那么总的排列数就是((n/2)!/(cnt[1]!*...*cnt[n]!)) 多重排列公式
- 对于每个字符,有全部取或者全部不取两种,因此可以用一个容量为n/2的01背包求出总的分配方案数
- 因为只有52个字符,所以可以预处理出任意两个字符的分配方案数
- 答案就是 (2*总排列数*分配方案数)
处理
- 累加方案数的时候反向处理,减去方案数的时候正向处理(常见)
即正常累加01背包的时候都是反着扫,但是用总方案减去非法方案的时候需要正着扫
- 附上线性逆元,阶乘,逆元阶乘打表板子
代码
#include<bits/stdc++.h>
#define P 1000000007
#define M 100005
#define ll long long
using namespace std;
ll f[60][60],c[60],inv[M],F[M],tp[M],dp[M],ans,Finv[M];
int i,j,x,y,q,n,l,r;
string s;
void init(){
cin>>s>>q;n=s.size();
F[0]=Finv[0]=inv[0]=1;
F[1]=Finv[1]=inv[1]=1;
for(i=2;i<M;i++){
inv[i]=inv[P%i]*(P-P/i)%P;
Finv[i]=Finv[i-1]*inv[i]%P;
F[i]=F[i-1]*i%P;
}
for(i=0;i<n;i++){
if(s[i]>='a'&&s[i]<='z')c[s[i]-'a'+1]++;
else c[s[i]-'A'+27]++;
}
ans=F[n/2]*F[n/2]%P;
for(i=1;i<=52;i++)
if(c[i])ans=ans*Finv[c[i]]%P;
dp[0]=1;
for(i=1;i<=52;i++)if(c[i])
for(j=n/2;j>=c[i];j--)dp[j]=(dp[j]+dp[j-c[i]])%P;
for(x=1;x<=52;x++){
for(y=1;y<=52;y++){
for(i=0;i<=n/2;i++)tp[i]=dp[i];
for(i=c[x];i<=n/2;i++)tp[i]=(tp[i]-tp[i-c[x]]+P)%P;
if(x!=y)for(i=c[y];i<=n/2;i++)tp[i]=(tp[i]-tp[i-c[y]]+P)%P;
f[x][y]=tp[n/2];
}
}
}
int main(){
init();
while(q--){
scanf("%d%d",&l,&r);
l--;r--;
if(s[l]>='a'&&s[l]<='z')l=s[l]-'a'+1;
else l=s[l]-'A'+27;
if(s[r]>='a'&&s[r]<='z')r=s[r]-'a'+1;
else r=s[r]-'A'+27;
printf("%lld
",2ll*ans%P*f[l][r]%P);
}
}