AtCoder Grand Contest 001 E BBQ Hard

都别拦我，我要放日语题面

E - BBQ Hard
時間制限 : 2sec / メモリ制限 : 256MB
配点 : 1400 点
問題文
高橋君はバーベキューをしようとしています。 バーベキューでは 2 本の串にいくつかの具材を刺した串焼きを 1 個作る予定です。
串焼きセットが N 個あり、i 番目のセットには串が 1 本、肉が Ai 個、野菜が Bi 個入っています。
セットを 2 個選び、セット 2 つに含まれる全ての具材を好きな順番で串 2 本に刺すことを考えます。 このとき、作ることの出来る串焼きは何通り考えられるでしょうか？ ただし、串どうしは区別でき、肉どうしや野菜どうしは区別できないものとします。 答えは非常に大きな数になる可能性があるので、109+7 で割った余りを求めてください。
制約
2≦N≦200,000
1≦Ai≦2000,1≦Bi≦2000
入力
入力は以下の形式で標準入力から与えられる。
N
A1 B1
A2 B2
:
AN BN
出力
作ることの出来る串焼きの種類数を 109+7 で割った余りを出力せよ。
入力例 1
Copy
3
1 1
1 1
2 1
出力例 1
Copy
26
図のような 26 通りの串焼きを作ることが出来ます。 灰色の棒は串を表しており、串に書かれた数はその串が含まれていたセットの*を表しています。 また、茶色の長方形は肉、緑色の長方形は野菜を表しています。

省选时好像有人讲过，反正就是转化成从(-x[i],-y[i])走到(x[j],y[j])的方案数，记得把自己到自己的方案减掉。

#include<cstdio>
#include<algorithm>
using namespace std;
#define Mod 1000000007
#define ll long long
inline char tc(void){
    static char fl[10000],*A=fl,*B=fl;
    return A==B&&(B=(A=fl)+fread(fl,1,10000,stdin),A==B)?EOF:*A++;
}
inline int read(void){
    int a=0;static char c;
    while((c=tc())<'0'||c>'9');
    while(c>='0'&&c<='9')a=a*10+c-'0',c=tc();
    return a;
}
ll fac[8005],inv[8005],n,f[4005][4005],x[200005],y[200005],ans,b[4005][4005];
inline ll C(ll n,ll m){
    return (fac[n]*inv[m]%Mod)*inv[n-m]%Mod;
}
int main(void){
    register int i,j;
    fac[0]=inv[0]=inv[1]=1;
    for(i=2;i<=8004;++i)    
        inv[i]=(Mod-Mod/i)*inv[Mod%i]%Mod;
    for(i=1;i<=8004;++i)
        fac[i]=fac[i-1]*i%Mod,inv[i]=inv[i-1]*inv[i]%Mod;
    n=read();
    for(i=1;i<=n;++i)
        x[i]=read(),y[i]=read(),++f[2001-x[i]][2001-y[i]],++b[2001+x[i]][2001+y[i]];
    for(i=1;i<=4004;++i)
        for(j=1;j<=4004;++j){
            f[i][j]=(f[i][j]+f[i-1][j]+f[i][j-1])%Mod;
            if(b[i][j])ans=(ans+b[i][j]*f[i][j]%Mod)%Mod;
        }
    for(i=1;i<=n;++i)
        ans=(((ans-C((x[i]+y[i])*2,x[i]*2)))%Mod+Mod)%Mod;
    printf("%d",ans*inv[2]%Mod);
    return 0;
}