C++14(g++5.4) 解法, 执行用时: 870ms, 内存消耗: 16096K, 提交时间: 2018-09-01 18:48:23

#include <iostream>
#include <stdio.h>
#define LL long long
const LL N = 105;
const LL mod = 1e9+7;
LL m[N],r[N],p[N];

LL dp[2][500020];
LL dv[2][500020];

int main()
{
	LL ni = 570000004;
	int n,L,M;
	scanf("%d%d%d",&n,&L,&M);
	LL sum=0;
	for(int i=1;i<=n;i++){
		scanf("%lld%lld%lld",&m[i],&r[i],&p[i]);
		r[i]=r[i]*ni%mod;
		p[i]=p[i]*ni%mod;
		sum+=m[i];
	}
	dp[0][0]=1;
	LL k=0;
	for(int i=1;i<=n;i++){
		for(int j=0;j<=sum;j++){
			dp[k^1][j]=(1-p[i]+mod)%mod*dp[k][j]%mod;
			if(j>=m[i])
				dp[k^1][j]=(dp[k^1][j]+dp[k][j-m[i]]*p[i]%mod)%mod;
			dv[k^1][j]=(1-p[i]+mod)%mod*dv[k][j]%mod;
			if(j>=m[i])
				dv[k^1][j]=(dv[k^1][j]+(dv[k][j-m[i]]+m[i]*r[i]%mod*dp[k][j-m[i]]%mod)*p[i]%mod)%mod;
		}
		k=k^1;
	}
	LL ans=0;
	for(int i=L;i<=sum;i++){
		ans+=dp[k][i]*M%mod-dv[k][i]+mod;
		ans%=mod;
	}
	printf("%lld\n",ans);
}

C++11(clang++ 3.9) 解法, 执行用时: 539ms, 内存消耗: 4292K, 提交时间: 2018-08-31 19:48:58

#include<bits/stdc++.h>
using namespace std;
#define MAXN 105
#define ll long long
#define P 1000000007
int n,m,x,y,i,j,ans,a[MAXN],b[MAXN],c[MAXN],f[500005],g[500005];
int main()
{
	scanf("%d%d%d",&n,&x,&y);
	for(i=1;i<=n;i++)
	{
		scanf("%d%d%d",a+i,b+i,c+i);
		b[i]=b[i]*570000004LL%P;
		c[i]=c[i]*570000004LL%P;
		m+=a[i];
	}
	for(f[0]=i=1;i<=n;i++)for(j=m;~j;j--)if(j>=a[i])
	{
		g[j]=((ll)(P+1-c[i])*g[j]+(g[j-a[i]]+(ll)f[j-a[i]]*a[i]%P*(b[i]+1))%P*c[i])%P;
		f[j]=((ll)(P+1-c[i])*f[j]+(ll)c[i]*f[j-a[i]])%P;
	}
	else
	{
		g[j]=(ll)(P+1-c[i])*g[j]%P;
		f[j]=(ll)(P+1-c[i])*f[j]%P;
	}
	for(i=x;i<=m;i++)ans=(ans+P-g[i]+(ll)f[i]*(y+i))%P;
	cout<<ans<<endl;
	return 0;
}