C++(g++ 7.5.0) 解法, 执行用时: 71ms, 内存消耗: 488K, 提交时间: 2023-08-09 11:39:00

#include <iostream>

using namespace std;

typedef long long LL;

const int N = 5e3 + 100, mod = 1e9 + 7;

int a[N], f[N], inv[N];

void init(int n)
{
    inv[1] = 1;
    for(int i = 2; i <= n; i ++)
        inv[i] = (LL)(mod - mod / i) * inv[mod % i] % mod;
}

int main()
{
    init(N - 1);

    int n, k;
    cin >> n >> k;

    for(int i = 1; i <= n; i ++)
        cin >> a[i];

    //计算(a1 - x) * (a2 - x) ... (an - x)
    f[0] = 1;
    for(int i = 1; i <= n; i ++)
    {
        for(int j = i; j > 0; j --)
            f[j] = ((LL)f[j] * a[i] % mod - f[j - 1] + mod) % mod;
        f[0] = (LL)f[0] * a[i] % mod;
    }

    int ans = 0;
    for(int i = 0, m = 1; i <= n; i ++)
    {
        ans = (ans + (LL)m * f[i] % mod) % mod;
        m = (LL)m * (k - i) % mod * inv[n] % mod;
    }   

    cout << (f[0] - ans + mod) % mod;

    return 0;
}

C++ 解法, 执行用时: 37ms, 内存消耗: 560K, 提交时间: 2021-11-28 19:21:42

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define Mod 1000000007
#define MN 5005
int ksm(int a,int x){
	int ans=1,w=a;
	while(x){
		if(x&1)ans=ans*w%Mod;
		w=w*w%Mod;
		x>>=1;
	}
	return ans;
}
int n,k,a[MN],f[MN];
signed main(){
	scanf("%lld%lld",&n,&k);
	f[0]=1;
	for(int i=1;i<=n;++i){
		scanf("%lld",&a[i]);
		for(int j=i;j;--j){
			f[j]=(f[j]*a[i]-f[j-1]+Mod)%Mod;
		}
		f[0]=f[0]*a[i]%Mod;
	}
	int res=0,tmp=1,inv=ksm(n,Mod-2);
	for(int i=0;i<=n;++i){
		res=(res+f[i]*tmp)%Mod;
		tmp=tmp*(k-i)%Mod*inv%Mod;
	}
	printf("%lld\n",(f[0]-res+Mod)%Mod);
	return 0;
}