AGC001E BBQ Hard

Link
不难发现({a_i+b_i+a_j+b_jchoose a_i+a_j})就是从((-a_i,-b_i))走到((a_j,b_j))的方案数。
然后直接(O(2000^2)dp)就行了。

#include<cstdio>
const int N=4007,M=200007,P=1000000007;
int f[N][N],g[N][N],a[M],b[M];
int read(){int x;scanf("%d",&x);return x;}
void inc(int&a,int b){a+=b-P,a+=a>>31&P;}
int main()
{
    int n=read(),ans=0;g[0][0]=1;
    for(int i=1;i<=n;++i) a[i]=read(),b[i]=read(),++f[2000-a[i]][2000-b[i]];
    for(int i=0;i<=4000;++i) for(int j=0;j<=4000;++j) inc(g[i][j],i? g[i-1][j]:0),inc(g[i][j],j? g[i][j-1]:0),inc(f[i][j],i? f[i-1][j]:0),inc(f[i][j],j? f[i][j-1]:0);
    for(int i=1;i<=n;++i) inc(ans,f[2000+a[i]][2000+b[i]]),inc(ans,P-g[a[i]*2][b[i]*2]);
    printf("%d
",(int)(ans*500000004ll%P));
}