题解 | #J题题解#

公式为 $ans = \sum_{k=0}^{n-1}\binom{n \space add \space k-1}{k} \cdot (\frac{p}{q})^n \cdot (1 - \frac{p}{q})^k$ ，其中的组合数可用形如 $C_{n}^{0}=1, C_{n}^{k}=C_{n-1}^{k-1} \cdot \frac{n}{k}$ 的递推式求出来。关键在于如何在5e6的条件下求出逆元，我用费马小定理WA了好几发，最后换成扩展欧几里德过了。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int mod=1e9+7;
int quick(int a,int b){
    int res=1;
    while(b){
        if(b&1){
            res=res*a%mod;
        }
        b>>=1;
        a=a*a%mod;
    }
    return res;
}
int exgcd(int a,int b,int &x,int &y){
    if (!b)
    {
        x = 1; y = 0;
        return a;   
    }
    int d = exgcd(b, a % b, x, y);
    int temp=y;   
    y=x-(a/b)*y;
    x=temp;
    return d;
}

int c[100007];//存组合数
void solve(){
    int n,p,q,sum=0;
    scanf("%lld%lld%lld",&n,&p,&q);
    c[0]=1;
    int d=(q-p)*quick(q,mod-2)%mod;
    int d2=p*quick(q,mod-2)%mod;
    int last=1;
    for(int i=0;i<=n-1;i++){
        int x,y;
        exgcd(i,mod,x,y);
        if(i!=0)c[i]=c[i-1]*(n+i-1)%mod*x%mod;
        sum=(sum+c[i]*last)%mod;
        last=last*d%mod;
    }
    sum=(sum*quick(d2,n))%mod;
    printf("%lld\n",(sum+mod)%mod);
}
signed main(){
    int t;
    scanf("%lld",&t);
    while(t--)solve();
}