题目概述

这题太水了，鸽了。

解题报告

这题太水了，鸽了。

答案就是 $\sum_{i=1}^{n}{n\choose i}p^i(1-p)^{n-i}\sum_{j=0}^{i-1}{n\choose j}q^j(1-q)^{n-j}$ ，稍微处理一下就是 $O(n)$ 啦。

示例程序

#include<cstdio>
using namespace std;
typedef long long LL;
const int maxn=10000000,MOD=1e9+7;

int n,A,B,P,Q,INVP,INVQ,INV[maxn+5],ans;

inline int Pow(int w,int b) {int s;for (s=1;b;b>>=1,w=(LL)w*w%MOD) if (b&1) s=(LL)s*w%MOD;return s;}
inline void AMOD(int &x,int tem) {if ((x+=tem)>=MOD) x-=MOD;}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%d",&n);INV[1]=1;for (int i=2;i<=n;i++) INV[i]=(LL)(MOD-MOD/i)*INV[MOD%i]%MOD;
    scanf("%d%d",&A,&B);P=(LL)A*Pow(B,MOD-2)%MOD;INVP=Pow((MOD+1-P)%MOD,MOD-2);
    scanf("%d%d",&A,&B);Q=(LL)A*Pow(B,MOD-2)%MOD;INVQ=Pow((MOD+1-Q)%MOD,MOD-2);
    for (int i=1,A=Pow((MOD+1-P)%MOD,n),B=Pow((MOD+1-Q)%MOD,n),C=0;i<=n;i++){
        A=(LL)A*(n-i+1)%MOD*INV[i]%MOD*P%MOD*INVP%MOD;AMOD(C,B);if (P==1&&i==n) A=1;
        AMOD(ans,(LL)A*C%MOD);B=(LL)B*(n-i+1)%MOD*INV[i]%MOD*Q%MOD*INVQ%MOD;
    }printf("%d\n",ans);return 0;
}