C++14(g++5.4) 解法, 执行用时: 3ms, 内存消耗: 376K, 提交时间: 2020-08-28 16:22:35

#include <bits/stdc++.h>
using namespace std;
#define MAXN 1000
#define MOD 100003
typedef long long ll;
ll quick_pow(ll x,ll y){
    if(y==0){
        return 1;
    }else if(y%2==0){
        ll nxt=quick_pow(x,y/2);
        return nxt*nxt%MOD;
    }else{
        ll nxt=quick_pow(x,y/2);
        return nxt*nxt%MOD*x%MOD;
    }
}
ll multi_inv(ll x){
    return quick_pow(x,MOD-2);
}
ll fac_dp[int(1e6+5)];
ll fac(ll x){
    if(x==0){
        return 1;
    }else if(fac_dp[x]){
        return fac_dp[x];
    }else{
        return fac_dp[x]=fac(x-1)*x%MOD;
    }
}
ll C(ll n,ll m){
    return fac(n)*multi_inv(fac(m)*fac(n-m)%MOD)%MOD;
}
ll f(ll n,ll m,ll k){
    if(k>n||k>m){
        return 0;
    }else{
        return C(n,k)*C(m,k)%MOD*fac(k)%MOD;
    }
}
int a,b,c,d,k;
int main(){
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    cin>>a>>b>>c>>d>>k;
    ll ans=0;
    for(int i=0;i<=k;i++){
        ans=(ans+f(a,b,i)*f(a+c-i,d,k-i)%MOD)%MOD;
    }
    cout<<ans<<endl;
    return 0;
}

C++(g++ 7.5.0) 解法, 执行用时: 3ms, 内存消耗: 492K, 提交时间: 2022-08-09 11:03:32

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

const int N = 2010, mod = 100003;
int fact[N], infact[N];

int qmi(int a, int b) {
	int res = 1;
	for (; b; b >>= 1, a = 1LL * a * a % mod) {
		if(b & 1) res = 1LL * res * a % mod;
	}
	return res;
}

int C(int a, int b) {
	if(a < b) return 0;
	return 1LL * fact[a] * infact[a - b] % mod * infact[b] % mod;
}

int P(int a, int b) {
	if(a < b) return 0;
	return 1LL * fact[a] * infact[a - b] % mod;
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	fact[0] = infact[0] = 1;
	for (int i = 1; i < N; i++) {
		fact[i] = 1LL * fact[i - 1] * i % mod;
		infact[i] = 1LL * infact[i - 1] * qmi(i, mod - 2) % mod;
	}
	
	int a, b, c, d, k;
	cin >> a >> b >> c >> d >> k;
	
	int res = 0;
	for (int i = 0; i <= k; i++) {
		res = (res + 1LL * C(b, i) * P(a, i) % mod * C(d, k - i) * P(a + c - i, k - i) % mod) % mod;
	}
	
	cout << res << "\n";
	
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 38ms, 内存消耗: 15992K, 提交时间: 2020-08-24 16:26:22

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int Mod=100003;
int a,b,c,d,k;
long long f[1001][2001],v[2001];
int main()
{int i,j;
    cin>>a>>b>>c>>d>>k;
    for (i=1;i<=c;i++)
    v[i]=d,f[0][i]=1;
    for (i=c+1;i<=a+c;i++)
    v[i]=b+d,f[0][i]=1;
    f[0][0]=1;
    for (j=1;j<=a+c;j++)
    for (i=1;i<=k;i++)
    f[i][j]=(f[i][j-1]+f[i-1][j-1]*(v[j]-i+1))%Mod;
    cout<<f[k][a+c];
}