智力测试 参考代码

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

typedef long long LL;
const int maxn = 200000 + 100;
const LL MOD = 1000000007;
int n, m, T, sr, sc, tr, tc;
int r[maxn], c[maxn], sortR[maxn], sortC[maxn];
LL multR[maxn], multC[maxn], addR[maxn], addC[maxn], fac[maxn], invFac[maxn];

LL fastPow(LL res, LL n) {
    LL ans;
    for (ans = 1; n != 0; n >>= 1) {
        if ((n & 1) == 1) {
            ans = ans * res % MOD;
        }
        res = res * res % MOD;
    }
    return ans;
}

LL inv(LL x) {
    return fastPow(x, MOD - 2);
}

void init() {
    fac[0] = 1;
    for (int i = 1; i < maxn; ++i) {
        fac[i] = fac[i - 1] * i % MOD;
    }
    invFac[maxn - 1] = inv(fac[maxn - 1]);
    for (int i = maxn - 2; i >= 0; --i) {
        invFac[i] = invFac[i + 1] * (i + 1) % MOD;
    }
}

LL C(LL n, LL m) {
    return fac[n] * invFac[n - m] % MOD * invFac[m] % MOD;
}

void solve(int *num, int n, LL *mult, LL *add) {
    sort(num + 1, num + 1 + n);
    mult[0] = 1;
    int r = 1;
    for (int l = 1; l <= n; l = r) {
        while (r <= n && num[r] == num[l]) {
            ++r;
        }
        mult[l] = mult[l - 1] * (r - l) % MOD;
        add[l] = add[l - 1] + 1;
        for (int i = l; i < r; ++i) {
            mult[i] = mult[l];
            add[i] = add[l];
        }
    }
}

int main() {
#ifdef ExRoc
    freopen("test.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false);

    init();
    cin >> n >> m >> T;
    for (int i = 1; i <= n; ++i) {
        cin >> r[i];
        sortR[i] = r[i];
    }
    for (int i = 1; i <= m; ++i) {
        cin >> c[i];
        sortC[i] = c[i];
    }
    solve(sortR, n, multR, addR);
    solve(sortC, m, multC, addC);

    while (T--) {
        cin >> sr >> sc >> tr >> tc;
        if (r[sr] > r[tr] || c[sc] > c[tc]) {
            cout << 0 << endl;
            continue;
        }
        if (sr != tr && r[sr] == r[tr]) {
            cout << 0 << endl;
            continue;
        }
        if (sc != tc && c[sc] == c[tc]) {
            cout << 0 << endl;
            continue;
        }
        LL mult = 1;
        int cn = 0;
        int cm = 0;
        if (sr != tr) {
            int idx1 = upper_bound(sortR + 1, sortR + 1 + n, r[sr]) - sortR;
            --idx1;
            int idx2 = lower_bound(sortR + 1, sortR + 1 + n, r[tr]) - sortR;
            --idx2;
            mult *= multR[idx2] * inv(multR[idx1]) % MOD;
            mult %= MOD;
            cn = cm = addR[idx2] - addR[idx1] + 1;
        }
        if (sc != tc) {
            int idx1 = upper_bound(sortC + 1, sortC + 1 + m, c[sc]) - sortC;
            --idx1;
            int idx2 = lower_bound(sortC + 1, sortC + 1 + m, c[tc]) - sortC;
            --idx2;
            mult *= multC[idx2] * inv(multC[idx1]) % MOD;
            mult %= MOD;
            cn += addC[idx2] - addC[idx1] + 1;
        }
        cout << mult * C(cn, cm) % MOD << endl;
    }

    return 0;
}