【组合计数】【DP】AGC001 BBQ Hard

分析：

首先，很容易得到一个简单的表达式：

观察一下这个式子有什么几何意义：
$C_{A_i+A_j+B_i+B_j}^{A_i+A_j}$可以表示从点$(-A_i,-B_i)$走到$(A_j,B_j)$的最短路径数！！！

所以这道题就可以DP来做了；

定义$dp[i][j]$表示从左下方走到$(i,j)$的最短路径数。

然后记$ask[i][j]$表示$A_x=i,B_x=j$的方案数。

答案就是$\sum_{0\leq i,j\leq 2000}ask_{i,j}*dp_{i,j}$

但是这时会将从自己$(-A_i,-B_i)$走到自己$(A_i,B_i)$的方案计算了，但这明显是不合法的

所以要减去这部分。即$\sum_{1\leq i\leq n}C_{2*A_i+2*B_i}^{2*A_i}$

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define SF scanf
#define PF printf
#define MAXN 100010
#define MAXM 4010
#define MOD 1000000007
using namespace std;
typedef long long ll;
int dp[MAXM][MAXM],ask[MAXM][MAXM];
ll fac[MAXM*2],inv[MAXM*2],del,ans;
ll fsp(ll x,int y){ll res=1;while(y){if(y&1)res=res*x%MOD;x=x*x%MOD;y>>=1;  }return res;
}
int n,u,v;
ll C(int n,int m){return fac[n]*inv[m]%MOD*inv[n-m]%MOD;  
}
int main(){fac[0]=1;for(int i=1;i<=8000;i++)fac[i]=fac[i-1]*i%MOD;inv[8000]=fsp(fac[8000],MOD-2);for(int i=8000;i>=1;i--)inv[i-1]=inv[i]*i%MOD;SF("%d",&n);for(int i=1;i<=n;i++){SF("%d%d",&u,&v);del+=C(2*u+2*v,2*u);del%=MOD;dp[2000-u][2000-v]++;ask[2000+u][2000+v]++;}for(int i=0;i<=4000;i++)for(int j=0;j<=4000;j++){if(i!=0)dp[i][j]+=dp[i-1][j];if(j!=0)dp[i][j]+=dp[i][j-1];dp[i][j]%=MOD;ans=(ans+1ll*ask[i][j]*dp[i][j])%MOD;}ans=(ans-del+MOD)%MOD;PF("%lld",ans*fsp(2,MOD-2)%MOD);
}