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\n",2ll*ans%P*f[l][r]%P);

	}

}