贝壳找房计数比赛

题目链接

2018 计蒜之道复赛--贝壳找房计数比赛

题解

高档题。提议大概是求字符串二在字符串一的全排列中出现的次数。
从字符串一中删去字符串二的个数之后求全排列数再乘以字符串二在字符串一中可能出现的位置数即可。通过乘法逆元避免高精度计算

代码

#include <cstdio>
#include <cstring>
typedef long long ll;
const ll mod=1000000007;
ll qp(ll a,ll b){
    ll ans=1;
    while(b){
        if(b&1)ans=ans*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans;
}
ll fac[100005];
char s1[100005],s2[100005],*s,*t;
int cnt[200];
int main(){
    int T,tot;ll ans;
    fac[0]=1;
    for(int i=1;i<=100000;i++)fac[i]=fac[i-1]*i%mod;
    scanf("%d",&T);
    while(T--){
        scanf("%s%s",s=s1,t=s2);
        memset(cnt,0,sizeof(cnt));
        tot=1;
        while(*s)cnt[*s++]++,tot++;
        while(*t)cnt[*t++]--,tot--;
        ans=fac[tot];
        for(int i='a';i<='z';i++){
            if(cnt[i]<0){ans=0;break;}
            if(fac[cnt[i]]!=1)ans=ans*qp(fac[cnt[i]],mod-2)%mod;
        }
        printf("%lld\n",ans);
    }
}

标签: none

添加新评论