C++14(g++5.4) 解法, 执行用时: 39ms, 内存消耗: 16228K, 提交时间: 2020-03-22 19:12:14

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 10;
const int mod = 1e9 + 7;
typedef long long ll;
ll fpow(ll a,ll b) {
    ll r = 1;
    while (b) {
        if (b & 1) r = 1ll * r * a % mod;
        b >>= 1;
        a = 1ll * a * a % mod;
    }
    return r;
}
ll n,m,k,p,fac[maxn],ifac[maxn],ans[maxn],sum;
ll C(int x,int y) {
    if (x < y || y < 0 || x < 0) return 0;
    return 1ll * fac[x] * ifac[y] % mod * ifac[x - y] % mod;
}
int main() {
    fac[0] = 1;
    for (int i = 1; i <= maxn - 10; i++)
        fac[i] = 1ll * fac[i - 1] * i % mod;
    ifac[maxn - 10] = fpow(fac[maxn - 10],mod - 2);
    for (int i = maxn - 10 - 1; i >= 0; i--)
        ifac[i] = 1ll * ifac[i + 1] * (i + 1) % mod;
    scanf("%lld%lld%lld%lld",&n,&m,&k,&p);
    ll q = 100 - p;
    ll t1 = 1ll * p * fpow(100,mod - 2) % mod, t2 = 1ll * q * fpow(100,mod - 2) % mod;
    ll siz = n * (n - 1) / 2;
    ll tot = C(n * (n - 1) / 2,m);                  //m对接触的所有情况
    for (int i = 1; i <= k; i++) {                   //枚举 i 个人带病毒
        ans[i] = 1ll * C(n,i) * fpow(t1,i) % mod * fpow(t2,n - i) % mod * fpow(tot,mod - 2) % mod * C(n - i,k - i) % mod;
        ll cnt = 0; ll s = 1;
        for (int j = k - i; j >= 0; j--) {
            cnt = (cnt + s * C(k - i,j) % mod * C(siz - i * (n - i - j),m) % mod) % mod;
            if (cnt < 0) cnt += mod;
            s *= -1;
        }
        ans[i] = 1ll * ans[i] * cnt % mod;
        sum = (sum + ans[i]) % mod;
    }
    for (int i = 1; i <= k; i++) {
        printf("%lld\n",ans[i] * fpow(sum,mod - 2) % mod);
    }
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 21ms, 内存消耗: 4220K, 提交时间: 2020-07-29 13:50:33

#include<bits/stdc++.h>
using namespace std;

const int mod=1e9+7;
long long one=1;
int A[500005],B[500005];
long long C(int n,int m)
{
	if(n<m)return 0;
	return one*A[n]*B[m]%mod*B[n-m]%mod;
}
long long fastpow(long long a,int b)
{
	long long s=1;
	for(;b;b>>=1,a=a*a%mod)if(b&1)s=s*a%mod;
	return s;
}
int main()
{
    int i,j,n,m,k,p,e,s=0,T[1005]={0};
    scanf("%d%d%d%d",&n,&m,&k,&p);
	p=p*fastpow(100,mod-2)%mod,e=n*(n-1)/2;
    for(A[0]=i=1;i<=e+5;i++)A[i]=one*A[i-1]*i%mod;
	B[e+5]=fastpow(A[e+5],mod-2);
	for(i=e+4;i>=0;i--)B[i]=one*B[i+1]*(i+1)%mod;
	for(i=1;i<=k;i++)
	{
		for(j=0;j<=k-i;j++)T[i]=(T[i]+(j&1?-1:1)*C(k-i,j)*C(e-i*(n-k+j),m)%mod+mod)%mod;
		T[i]=T[i]*C(n-i,k-i)%mod*fastpow(C(e,m),mod-2)%mod*C(n,i)%mod*fastpow(p,i)%mod*fastpow((1-p+mod)%mod,n-i)%mod;
		s=(s+T[i])%mod;
	}
	s=fastpow(s,mod-2);
	for(i=1;i<=k;i++)printf("%d\n",one*T[i]*s%mod);
    return 0;
}