[数学记录]AT1983 [AGC001E] BBQ Hard
command_block
2021-02-28 19:53:17
**题意** ： 给出 $n$ 个数对 $(a_i,b_i)$ ，求下列式子的值 ：
$$\sum\limits_{i=1}^n\sum\limits_{j=i+1}^n\dbinom{a_i+a_j+b_i+b_j}{a_i+a_j}$$
答案对 $10^9+7$ 取模。
$n\leq 2\times 10^5,a_i,b_i\leq 2000$ ，时限$\texttt{2s}$。
------------
发现 $a,b$ 较小，从此处入手。
为 $\binom{n+m}{n,m}$ 编一个组合意义 ： 从 $(0,0)$ 出发，只能向上或向右走，到达 $(n,m)$ 的方案数。
于是，题目中所求的式子就可以看做 ： 从 $(0,0)$ 出发，到达 $(a_i+a_j,b_i+b_j)$ 的方案数。
平移一下，即改为 ： 从 $(-a_i,-b_i)$ 出发，到达 $(a_j,b_j)$ 的方案数。
于是可以改为计算两两点之间的路径条数总和。减去 $i=j$ 的贡献后除以 $2$ 即可
设 $o[x,y]$ 为到达 $(x,y)$ 的路径条数，则有如下转移 ：
$$o[x,y]=o[x-1,y]+o[x,y-1]+\sum_i[(-a_i,-b_i)=(x,y)]$$
复杂度为 $O(ab+n)$。
```cpp
#include<algorithm>
#include<cstdio>
#define MaxM 200500
#define MaxN 4050
#define ll long long
using namespace std;
const int mod=1000000007,det=2001;
ll powM(ll a,int t=mod-2){
ll ret=1;
while(t){
if (t&1)ret=ret*a%mod;
a=a*a%mod;t>>=1;
}return ret;
}
ll fac[MaxN<<1],ifac[MaxN<<1];
ll C(int n,int m)
{return fac[n]*ifac[m]%mod*ifac[n-m]%mod;}
void Init(int n)
{
fac[0]=1;
for (int i=1;i<=n;i++)
fac[i]=fac[i-1]*i%mod;
ifac[n]=powM(fac[n]);
for (int i=n;i;i--)
ifac[i-1]=ifac[i]*i%mod;
}
struct Data{int a,b;}s[MaxM];
int m,o[MaxN][MaxN];
int main()
{
scanf("%d",&m);
for (int i=1;i<=m;i++){
scanf("%d%d",&s[i].a,&s[i].b);
o[det-s[i].a][det-s[i].b]++;
}
Init(8000);
for (int i=1;i<=4002;i++)
for (int j=1;j<=4002;j++)
o[i][j]=(o[i][j]+o[i-1][j]+o[i][j-1])%mod;
int ans=0;
for (int i=1;i<=m;i++){
ans=(ans+o[det+s[i].a][det+s[i].b])%mod;
ans=(ans-C((s[i].a+s[i].b)*2,s[i].a*2))%mod;
}ans=1ll*(ans+mod)*((mod+1)/2)%mod;
printf("%d",ans);
return 0;
}
```