题目描述

输入

输出

样例输入

4 3 5

4 1 7 3

4 7 4 8

样例输出

59716

数据范围

解法

40%暴力即可；

60%依然暴力；

100%依次计算第一行和第一列对答案的贡献即可：

可以知道f[i][j]对答案的贡献=a^(n-i)*b^(n-j)*C(n-i+n-j,n-j)

然后利用逆元计算组合数，快速幂快速算出答案即可。

代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

#define ll long long

#define sqr(x) ((x)*(x))

#define ln(x,y) ll(log(x)/log(y))

using namespace std;

const char* fin="aP1.in";

const char* fout="aP1.out";

const ll inf=0x7fffffff;

const ll maxn=100007;

const ll mo=1000000007;

ll n,m1,m2,i,j,k;

ll ans,f[maxn*2];

ll qpower(ll a,ll b){

    ll c=1;

    while (b){

        if (b%2) c=(c*a)%mo;

        a=(a*a)%mo;

        b/=2;

    }

    return c;

}

ll niyuan(ll a){

    return qpower(a,mo-2);

}

ll c(ll a,ll b){

    return f[a]*niyuan(f[b])%mo*niyuan(f[a-b])%mo;

}

int main(){

    scanf("%d%d%d",&n,&m1,&m2);

    f[0]=1;

    for (i=1;i<=n*2;i++) f[i]=f[i-1]*i%mo;

    for (i=1;i<=n;i++) {

        scanf("%d",&j);

        if (i>1) ans=(ans+qpower(m1,n-1)*qpower(m2,n-i)%mo*j%mo*c(n-2+n-i,n-2))%mo;

    }

    for (i=1;i<=n;i++) {

        scanf("%d",&j);

        if (i>1) ans=(ans+qpower(m1,n-i)*qpower(m2,n-1)%mo*j%mo*c(n-2+n-i,n-2))%mo;

    }

    printf("%lld",ans);

    return 0;

}