[AGC001E]BBQ Hard 组合数学

题目描述

Snuke is having another barbeque party.

This time, he will make one serving of Skewer Meal.

He has a stock of N Skewer Meal Packs. The i-th Skewer Meal Pack contains one skewer, Ai pieces of beef and Bi pieces of green pepper. All skewers in these packs are different and distinguishable, while all pieces of beef and all pieces of green pepper are, respectively, indistinguishable.

To make a Skewer Meal, he chooses two of his Skewer Meal Packs, and takes out all of the contents from the chosen packs, that is, two skewers and some pieces of beef or green pepper. (Remaining Skewer Meal Packs will not be used.) Then, all those pieces of food are threaded onto both skewers, one by one, in any order.

(See the image in the Sample section for better understanding.)

In how many different ways can he make a Skewer Meal? Two ways of making a Skewer Meal is different if and only if the sets of the used skewers are different, or the orders of the pieces of food are different. Since this number can be extremely large, find it modulo 109+7.

Constraints
2≦N≦200,000
1≦Ai≦2000,1≦Bi≦2000

输入

The input is given from Standard Input in the following format:

N
A1 B1
A2 B2
:
AN BN

输出

Print the number of the different ways Snuke can make a serving of Skewer Meal, modulo 109+7.

样例输入

样例输出

提示

The 26 ways of making a Skewer Meal are shown below. Gray bars represent skewers, each with a number denoting the Skewer Meal Set that contained the skewer. Brown and green rectangles represent pieces of beef and green pepper, respectively.

题意：

有n个背包，第i个背包里有一个编号为 $i$

当且仅当至少有一根棍子的编号不同或者是肉和菜的数目不同或者是排列方式不同时，称这两种烤串是不同的。

 1 #include <bits/stdc++.h>
 2 
 3 const int maxn = int(4e4) + 7, mod = int(1e9) + 7;
 4 typedef long long ll;
 5 ll fac[maxn], inv[maxn];
 6 
 7 ll power_mod(ll p, ll q) {
 8     ll ret = 1;
 9     while (q) {
10         if (q & 1) ret = ret * p % mod;
11         p = p * p % mod;
12         q >>= 1;
13     }
14     return ret;
15 }
16 
17 void init() {
18     fac[0] = 1;
19     for (int i = 1; i <= maxn - 10; ++i) fac[i] = fac[i - 1] * i % mod;
20     inv[maxn - 10] = power_mod(fac[maxn - 10], mod - 2);
21     for (int i = maxn - 11; i >= 0; --i) inv[i] = inv[i + 1] * (i + 1) % mod;
22 }
23 
24 ll C(int x, int y) {
25     return fac[x] * inv[y] % mod * inv[x - y] % mod;
26 }
27 
28 int n, a[2000007], b[2000007], dp[4007][4007];
29 
30 int main() {
31 //    freopen("in.txt", "r", stdin);
32     init();
33     scanf("%d", &n);
34     for (int i = 1; i <= n; i++) {
35         scanf("%d%d", a + i, b + i);
36         dp[2001 - a[i]][2001 - b[i]]++;
37     }
38     for (int i = 1; i <= 4001; i++)
39         for (int j = 1; j <= 4001; j++) {
40             dp[i][j] = (dp[i][j] + dp[i - 1][j]) % mod;
41             dp[i][j] = (dp[i][j] + dp[i][j - 1]) % mod;
42         }
43     ll ans = 0;
44     for (int i = 1; i <= n; i++) ans = (ans + dp[2001 + a[i]][2001 + b[i]]) % mod;
45     for (int i = 1; i <= n; i++) ans = (ans - C(a[i] + a[i] + b[i] + b[i], a[i] + a[i]) + mod) % mod;
46     printf("%lld
", ans * power_mod(2, mod - 2) % mod);
47     return 0;
48 }