计数题萌萌哒~
这道题其实就是统计 \(\sum_{i=1}^{n}\sum_{j=i+1}^{n}C\binom{a[i] + a[j]}{a[i] + a[j] + b[i] + b[j]}\) 。这个式子不是很好统计,我们可以转化一下:
\((\sum_{i=1}^{n}\sum_{j=i+1}^{n}C\binom{a[i] + a[j]}{a[i] + a[j] + b[i] + b[j]} - \sum_{i = 1}^{n}C\binom{2 * a[i]}{2 * a[i] + 2 * b[i]}) / 2\)
这样的话,我们只需要考虑如何统计前一部分的贡献即可。前一部分的贡献是多少呢?就是平面上所有的点 \((-a[j], -b[j])\) 到达 \((a[i],b[i])\) 的方案数。这个我们可以 \(a[i]^{2}\)的 dp 统计。**启示:有时缩小限制好,有时放宽限制容斥计算大法好哇~~
#includeusing namespace std;#define maxn 2500000#define mod 1000000007#define maxm 4020#define int long longint n, a[maxn], b[maxn], inv[maxn], fac[maxn];int ans, m, S = 2005, f[maxm][maxm];int read(){ int x = 0, k = 1; char c; c = getchar(); while(c < '0' || c > '9') { if(c == '-') k = -1; c = getchar(); } while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * k;}void Up(int &x, int y) { x = (x + y) % mod; }int C(int n, int m){ if(n < m || m < 0 || n < 0) return 0; return fac[n] * inv[m] % mod * inv[n - m] % mod;}void pre(){ fac[0] = fac[1] = 1; inv[0] = inv[1] = 1; for(int i = 2; i < maxn; i ++) fac[i] = fac[i - 1] * i % mod; for(int i = 2; i < maxn; i ++) inv[i] = (mod - mod / i) * inv[mod % i] % mod; for(int i = 2; i < maxn; i ++) inv[i] = inv[i] * inv[i - 1] % mod;}signed main(){ pre(); n = read(); for(int i = 1; i <= n; i ++) { a[i] = read(), b[i] = read(); f[-a[i] + S][-b[i] + S] ++; } m = 2 * S; for(int i = 1; i <= m; i ++) for(int j = 1; j <= m; j ++) Up(f[i][j], (f[i - 1][j] + f[i][j - 1]) % mod); for(int i = 1; i <= n; i ++) { Up(ans, f[a[i] + S][b[i] + S]); Up(ans, mod - C(2 * (a[i] + b[i]), 2 * a[i])); } printf("%lld\n", ans * inv[2] % mod); return 0;}