车的放置

LibreOJ-10232-车的放置

实现

#include <iostream>
using namespace std;

typedef long long LL;
const int N = 2010, M = 100003;
int a, b, c, d, k;
int f[N], inv_f[N];

int power (int a, int b, int p) {
    int res = 1 % p;
    while (b > 0) {
        if (b & 1) res = (LL)res * a % p;
        a = (LL)a * a % p;
        b /= 2;
    }
    return res;
}
void initialize () {
    f[0] = inv_f[0] = 1;
    for (int i = 1; i < N; ++ i) {
        f[i] = (LL)i * f[i - 1] % M;
        inv_f[i] = (LL)power(i, M - 2, M) * inv_f[i - 1] % M;
    }
}
int C (int n, int m) {
    if (m > n) return 0;
    return (LL)f[n] * inv_f[m] % M * inv_f[n - m] % M;
}
int P (int n, int m) {
    if (m > n) return 0;
    return (LL)f[n] * inv_f[n - m] % M;
}

int main () {
    initialize();

    cin >> a >> b >> c >> d >> k;
    
    int res = 0;
    for (int i = 0; i <= k; ++ i) {
        int x = (LL)C(b, i) * P(a, i) % M,
            y = (LL)C(d, k - i) * P(a + c - i, k - i) % M;
        res = (res + (LL)x * y % M) % M;
    }
    cout << res << endl;
    return 0;
}