从零开始的数数大学习

cjdst

2026-03-22 21:44:14

发布于：广东

5阅读

0回复

0点赞

我真零基础啊

P6146

Difficulty：3.2 / Easy

这题我怎么都做这么吃力啊。

拆成上半部分和下半部分。

注意到上半部分所有放 $i$ 个的情况等价。所以考虑枚举 $i$ 。

上半部分的情况数是 ${a\choose i}{b\choose i}i!$ ，下半部分情况数是 ${a+c-i\choose k-i}{d-i\choose k-i}(k-i)!$ ，乘起来即可。

namespace cjdst{
    const ll N = 2000, mod = 100003;
	
	ll frac[N + 5], invfrac[N + 5];
	
	ll ksm(ll x, ll y){
		ll ans = 1;
		while(y){
			if(y & 1) ans = ans * x % mod;
			x = x * x % mod, y >>= 1; 
		}
		return ans;
	}
    
    void init(){
		std::ios::sync_with_stdio(0);
		std::cin.tie(0);
		std::cout.tie(0);
		frac[0] = 1;
		for(int i = 1; i <= N; i++){
			frac[i] = frac[i - 1] * i % mod;
		}
		invfrac[N] = ksm(frac[N], mod - 2);
		for(int i = N - 1; i >= 0; i--){
			invfrac[i] = invfrac[i + 1] * (i + 1) % mod;
		}
	}
	
	ll A(ll n, ll m){
		if(m > n) return 0;
		return frac[n] * invfrac[n - m] % mod; 
	}
	
	ll C(ll n, ll m){
		if(m > n) return 0;
		return frac[n] * invfrac[m] % mod * invfrac[n - m] % mod;
	}

	void solve(){
		int a, b, c, d, k;
		std::cin >> a >> b >> c >> d >> k;
		ll ans = 0;
		for(int i = 0; i <= k; i++){
			ans += A(a, i) * C(b, i) % mod * A(a + c - i, k - i) % mod * C(d, k - i) % mod;
			ans %= mod;
		}
		std::cout << ans << '\n';
	}
}