BBQ Hard
题解
首先，我们可以考虑组合数是可以被表示成路径的形式的，
(
n
+
m
m
)
\binom{n+m}{m}
(mn+m)可以表示从点
(
0
,
0
)
(0,0)
(0,0)到点
(
n
,
m
)
(n,m)
(n,m)的简单路径(向上走或向右走)数。
那么显然，我们
(
a
i
+
a
j
+
b
i
+
b
j
a
i
+
a
j
)
\binom{a_i+a_j+b_i+b_j}{a_i+a_j}
(ai+ajai+aj+bi+bj)可以表示从点
(
0
,
0
)
(0,0)
(0,0)到点
(
a
i
+
a
j
,
b
i
+
b
j
)
(a_i+a_j,b_i+b_j)
(ai+aj,bi+bj)的简单路径数量。但显然
我们不可能对于每个
(
a
i
+
a
j
,
b
i
+
b
j
)
(a_i+a_j,b_i+b_j)
(ai+aj,bi+bj)都求一条路径，但不妨再观察一下，
(
0
,
0
)
(0,0)
(0,0)到
(
a
i
+
a
j
,
b
i
+
b
j
)
(a_i+a_j,b_i+b_j)
(ai+aj,bi+bj)的路径条数显然是等价于
(
−
a
i
,
−
b
i
)
(-a_i,-b_i)
(−ai,−bi)到
(
a
j
,
b
j
)
(a_j,b_j)
(aj,bj)的路径数的。
我们可以用
d
p
dp
dp求出所有的
(
−
a
i
,
−
b
i
)
(-a_i,-b_i)
(−ai,−bi)到所有的
(
a
j
,
b
j
)
(a_j,b_j)
(aj,bj)的路径数。
记
d
p
x
,
y
dp_{x,y}
dpx,y为所有的
(
−
a
i
,
−
b
i
)
(-a_i,-b_i)
(−ai,−bi)到点
(
x
,
y
)
(x,y)
(x,y)的简单路径数，
∑
j
=
1
n
d
p
a
i
,
b
i
\sum_{j=1}^{n}dp_{a_i,b_i}
∑j=1ndpai,bi就是答案。
时间复杂度 O ( n + A B ) O\left(n+AB\right) O(n+AB)。
源码
#include<bits/stdc++.h>
using namespace std;
#define MAXN 200005
#define MAXM 4005
#define lowbit(x) (x&-x)
#define reg register
#define pb push_back
#define mkpr make_pair
#define fir first
#define sec second
typedef long long LL;
typedef unsigned long long uLL;
typedef long double ld;
typedef pair<int,int> pii;
const int INF=0x3f3f3f3f;
const int mo=1e9+7;
const int mod=1e5+3;
const int inv2=5e8+4;
const int jzm=2333;
const int zero=2000;
const int n1=1000;
const int M=100000;
const int orG=3,ivG=332748118;
const long double Pi=acos(-1.0);
const double eps=1e-12;
template<typename _T>
_T Fabs(_T x){return x<0?-x:x;}
template<typename _T>
void read(_T &x){
_T f=1;x=0;char s=getchar();
while(s>'9'||s<'0'){if(s=='-')f=-1;s=getchar();}
while('0'<=s&&s<='9'){x=(x<<3)+(x<<1)+(s^48);s=getchar();}
x*=f;
}
template<typename _T>
void print(_T x){if(x<0){x=(~x)+1;putchar('-');}if(x>9)print(x/10);putchar(x%10+'0');}
int gcd(int a,int b){return !b?a:gcd(b,a%b);}
int add(int x,int y,int p){return x+y<p?x+y:x+y-p;}
void Add(int &x,int y,int p){x=add(x,y,p);}
int qkpow(int a,int s,int p){int t=1;while(s){if(s&1)t=1ll*t*a%p;a=1ll*a*a%p;s>>=1;}return t;}
int n,a[MAXN],b[MAXN],dp[MAXM][MAXM],ans,fac[MAXM*2],inv[MAXM*2],ff[MAXM*2];
void init(){
fac[0]=fac[1]=inv[0]=inv[1]=ff[1]=1;
for(int i=2;i<=8000;i++)
fac[i]=1ll*i*fac[i-1]%mo,
ff[i]=1ll*(mo-mo/i)*ff[mo%i]%mo,
inv[i]=1ll*ff[i]*inv[i-1]%mo;
}
int C(int x,int y){
if(x<y||x<0||y<0)return 0;
return 1ll*fac[x]*inv[y]%mo*inv[x-y]%mo;
}
signed main(){
read(n);init();
for(int i=1;i<=n;i++)read(a[i]),read(b[i]),dp[zero-a[i]][zero-b[i]]++;
for(int i=1;i<=8000;i++)
for(int x=max(0,i-4000),y=min(4000,i);x<=4000&&y>=0;x++,y--){
if(x)Add(dp[x][y],dp[x-1][y],mo);
if(y)Add(dp[x][y],dp[x][y-1],mo);
}
for(int i=1;i<=n;i++)
Add(ans,dp[zero+a[i]][zero+b[i]],mo),
Add(ans,mo-C(2*(a[i]+b[i]),2*a[i]),mo);
printf("%d\n",1ll*inv2*ans%mo);
return 0;
}