C++(g++ 7.5.0) 解法, 执行用时: 524ms, 内存消耗: 24100K, 提交时间: 2023-06-20 10:11:02

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e6 + 5;
ll inv[maxn], invfac[maxn], fac[maxn];
const ll mod = 1e9 + 7;
void pre() {
	inv[0] = invfac[0] = 1;
	inv[1] = invfac[1] = 1;
	fac[1] = 1;
	for (ll i = 2; i <= 1e6; i++) {
		inv[i] = (mod - mod / i) * inv[mod % i] % mod;
		invfac[i] = invfac[i - 1] * inv[i] % mod;
		fac[i] = fac[i - 1] * i % mod;//递推逆元以及阶乘逆元, (虽然不常用)
	}
}
ll C(ll n, ll m) {
	return fac[n] * invfac[m] % mod * invfac[n - m] % mod;
}
signed main() {
	pre();
	ll m, x, y, p;
	while (std::cin >> m >> x >> y >> p) {
		if (x == 1 or y == 0) {
			cout << p << endl;
			continue;
		}
		ll ans = 0;
		for (ll i = 0; i <= y; i++) {
			ans = (ans + C(x - 1, i)) % mod;
		}
		ans = ans * p % mod;
		cout << ans << endl;
	}
	return 0;
}

C++14(g++5.4) 解法, 执行用时: 776ms, 内存消耗: 560K, 提交时间: 2020-05-11 19:48:45

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn=10005;
const int mod=1e9+7;
int inv[maxn];
void initial(const int n=1e4)
{
	inv[0]=inv[1]=1;
	for(int i=2;i<=n;i++) inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
	for(int i=2;i<=n;i++) inv[i]=1ll*inv[i]*inv[i-1]%mod;
}
int _pow(int a,int n)
{
	int res=1; a%=mod;
	while(n)
	{
		if(n&1) res=1ll*res*a%mod;
		a=1ll*a*a%mod;
		n>>=1;
	}
	return res;
}
int main(void)
{
	initial();
	int m,x,y,p;
	while(scanf("%d%d%d%d",&m,&x,&y,&p)!=EOF)
	{
		int res;
		if(y>=x) 
		{
			res=_pow(2,x-1);
		}
		else
		{
			x--;
			int fz=1;  res=0;
			for(int i=x,j=0;j<=y;i--,j++)
			{
				res=(res+1ll*fz*inv[j]%mod)%mod;
				fz=1ll*fz*i%mod;
			}
		}
		printf("%d\n",1ll*res*p%mod);
	}
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 805ms, 内存消耗: 12304K, 提交时间: 2019-07-19 20:05:01

#include<bits/stdc++.h>
#define mod 1000000007
using namespace std;
int m,x,y,p,L;
int inv[1000005],ans;
int ifac[1000005],fac[1000005];

int main(){
	inv[1]=1;
	for(int i=2;i<=1000000;i++) inv[i]=1LL*(mod-mod/i)*inv[mod%i]%mod;
	ifac[0]=fac[0]=1;
	for(int i=1;i<=1000000;i++){
		ifac[i]=1LL*ifac[i-1]*inv[i]%mod;
		fac[i]=1LL*fac[i-1]*i%mod;
	}
	while(scanf("%d %d %d %d",&m,&x,&y,&p)!=EOF){
		ans=0;
		L=min(x-1,y);
		for(int i=0;i<=L;i++) (ans+=1LL*fac[x-1]*(1LL*ifac[i]*ifac[(x-1)-i]%mod)%mod)%=mod;
		printf("%d\n",1LL*ans*p%mod);
	}
	
	return 0;
}