【智力测试——二分、前缀和、乘法逆元、组合计数】

题目

代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int mod = 1e9 + 7;
const int N = 1e5 + 10;
int r[N], c[N], f[2 * N];
int nr[N], nc[N], nn, nm;
int cntr[N], cntc[N];
int n, m, t;void init(int n) {f[0] = f[1] = 1;for (int i = 2; i <= n; i++)f[i] = (ll)f[i - 1] * i % mod;
}ll qmi(ll base, int expo) {ll retv = 1;while (expo) {if (expo & 1)retv = retv * base % mod;base = base * base % mod;expo >>= 1;}return retv;
}void discretize() {int last = -1;for(int i = 1; i <= n; i++) {if(nr[i] > last) ++nn, cntr[nn]++, last = nr[i];else cntr[nn]++;}last = -1;for(int i = 1; i <= m; i++) {if(nc[i] > last) ++nm, cntc[nm]++, last = nc[i];else cntc[nm]++;}cntr[0] = 1;for(int i = 1; i <= nn; i++)cntr[i] = (ll)cntr[i] * cntr[i-1] % mod;cntc[0] = 1;for(int i = 1; i <= nm; i++)cntc[i] = (ll)cntc[i] * cntc[i-1] % mod;nn = unique(nr+1, nr+n+1) - nr - 1;nm = unique(nc+1, nc+m+1) - nc - 1;
}int main() {ios::sync_with_stdio(0);cin.tie(0);init(2e5);cin >> n >> m >> t;for (int i = 1; i <= n; i++)cin >> r[i], nr[i] = r[i];for (int i = 1; i <= m; i++)cin >> c[i], nc[i] = c[i];sort(nr + 1, nr + n + 1);sort(nc + 1, nc + m + 1);discretize();while (t--) {int sr, sc, tr, tc;cin >> sr >> sc >> tr >> tc;if ((r[tr] <= r[sr] && tr != sr) || (c[tc] <= c[sc] && tc != sc)) {cout << 0 << '\n';continue;}int srp = lower_bound(nr + 1, nr + nn + 1, r[sr]) - nr;int trp = lower_bound(nr + 1, nr + nn + 1, r[tr]) - nr;int scp = lower_bound(nc + 1, nc + nm + 1, c[sc]) - nc;int tcp = lower_bound(nc + 1, nc + nm + 1, c[tc]) - nc;int drp = trp - srp;int dcp = tcp - scp;int ans = (ll)f[drp + dcp] * qmi(f[drp], mod - 2) % mod * qmi(f[dcp], mod - 2) % mod;if(drp) ans = (ll)ans * cntr[trp-1] % mod * qmi(cntr[srp], mod-2) % mod;if(dcp) ans = (ll)ans * cntc[tcp-1] % mod * qmi(cntc[scp], mod-2) % mod;cout << ans << '\n';}
}