题目
思路
显然就是求
∑
i
<
j
(
a
i
+
b
i
+
a
j
+
b
j
a
i
+
a
j
)
\sum_{i<j}{a_i+b_i+a_j+b_j\choose a_i+a_j}
i<j∑(ai+ajai+bi+aj+bj)
我将问题转化了一下：有多少种方案从原点走到
(
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) 的想法。稍微推了一下，感觉更像是变下指标求和。于是
∑
i
<
j
(
a
i
+
b
i
+
a
j
+
b
j
a
i
+
a
j
)
=
∑
i
,
j
∑
k
(
a
i
+
b
i
k
)
(
a
j
+
b
j
a
i
+
a
j
−
k
)
=
∑
i
,
k
(
a
i
+
b
i
k
)
∑
j
(
a
j
+
b
j
a
j
+
a
i
−
k
)
\begin{aligned} &\sum_{i<j}{a_i+b_i+a_j+b_j\choose a_i+a_j}\\ =&\sum_{i,j}\sum_k{a_i+b_i\choose k}{a_j+b_j\choose a_i+a_j-k}\\ =&\sum_{i,k}{a_i+b_i\choose k}\sum_{j}{a_j+b_j\choose a_j+a_i-k}\\ \end{aligned}
==i<j∑(ai+ajai+bi+aj+bj)i,j∑k∑(kai+bi)(ai+aj−kaj+bj)i,k∑(kai+bi)j∑(aj+ai−kaj+bj)
这个推导看上去很离谱，但也还有迹可循：相当于特殊的 “单独求贡献” 方法。
后面的求和只与 ( a i − k ) (a_i-k) (ai−k) 有关，可以枚举之后预处理。前面枚举 i , k i,k i,k 后直接调用，时间复杂度 O ( n a ) \mathcal O(na) O(na) 。需要卡常，比如减少乘法的次数（多个数的 ( a i − k ) (a_i-k) (ai−k) 相同时，左边组合数先求和，再做乘法，可以显著提高效率）。
代码
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cctype>
using namespace std;
# define rep(i,a,b) for(int i=(a); i<=(b); ++i)
# define drep(i,a,b) for(int i=(a); i>=(b); --i)
typedef long long llong;
inline int readint(){
int a = 0, c = getchar(), f = 1;
for(; !isdigit(c); c=getchar())
if(c == '-') f = -f;
for(; isdigit(c); c=getchar())
a = (a<<3)+(a<<1)+(c^48);
return a*f;
}
const int MOD = 1e9+7;
inline int modAdd(int x,const int y){
return ((x += y) >= MOD) ? (x-MOD) : x;
}
const int MAXA = 2000, MAXN = 200005;
int c[MAXA<<2|1][MAXA<<2|1], val[MAXA<<1|1];
int a[MAXN], b[MAXN], coe[MAXA<<1|1];
int main(){
int n = readint(), ans = 0;
rep(i,0,MAXA<<2) rep(j,c[i][0]=1,i)
c[i][j] = modAdd(c[i-1][j-1],c[i-1][j]);
rep(i,1,n) a[i] = readint(), b[i] = readint();
rep(j,1,n) rep(i,-a[j],MAXA) val[i+MAXA] =
modAdd(val[i+MAXA],c[a[j]+b[j]][a[j]+i]);
for(int i=1; i<=n; ++i){
const int *shit = c[a[i]+b[i]]+(a[i]+b[i])+1;
for(int *v=coe-b[i]+MAXA,*jb=c[a[i]+b[i]]; jb!=shit;
++v,++jb) *v = modAdd(*v,*jb); // coefficient
}
rep(i,0,MAXA<<1) ans = int((ans+llong(val[i])*coe[i])%MOD);
rep(i,1,n){ // except i = j
ans -= c[(a[i]+b[i])<<1][a[i]<<1];
if(ans < 0) ans += MOD; // keep positive
}
ans = int((llong(MOD+1)>>1)*ans%MOD);
printf("%d\n",ans);
return 0;
}
正解
上面的那个向量相加，太糟糕了。事实上，它还等价于 ( − a i , − b i ) (-a_i,-b_i) (−ai,−bi) 走到 ( a j , b j ) (a_j,b_j) (aj,bj) 的方案数！
这两个方案的区别是什么呢？我是让起点都落在原点上，也就是较少的起点；而这个做法是固定起点，虽然有较多的起点。要知道， d p \tt dp dp 喜欢固定而不是少。多与少，只是 d p \tt dp dp 值的关系；而不固定，则是 d p \tt dp dp 状态的事儿。我们要让信息熵足够小。
于是就是一个类似多源点路径方案的东西。在 O ( a 2 ) \mathcal O(a^2) O(a2) 范围内暴力递推即可。
代码
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cctype>
using namespace std;
# define rep(i,a,b) for(int i=(a); i<=(b); ++i)
# define drep(i,a,b) for(int i=(a); i>=(b); --i)
typedef long long llong;
inline int readint(){
int a = 0, c = getchar(), f = 1;
for(; !isdigit(c); c=getchar())
if(c == '-') f = -f;
for(; isdigit(c); c=getchar())
a = (a<<3)+(a<<1)+(c^48);
return a*f;
}
const int MOD = 1e9+7;
inline int modAdd(int x,const int y){
return ((x += y) >= MOD) ? (x-MOD) : x;
}
const int MAXA = 2000;
int jc[MAXA<<2|1], inv[MAXA<<2|1];
void prepare(int n = MAXA<<2){
rep(i,(jc[0]=inv[0]=jc[1]=inv[1]=1)+1,n){
jc[i] = int(llong(jc[i-1])*i%MOD);
inv[i] = int(llong(MOD-MOD/i)*inv[MOD%i]%MOD);
}
rep(i,2,n) inv[i] = int(llong(inv[i-1])*inv[i]%MOD);
}
int getC(int n,int m){
return int(llong(jc[n])*inv[m]%MOD*inv[n-m]%MOD);
}
const int MAXN = 200005;
int x[MAXN], y[MAXN], dp[MAXA<<1|1][MAXA<<1|1];
int main(){
prepare();
int n = readint(), ans = 0;
rep(i,1,n){
x[i] = readint(), y[i] = readint();
++ dp[MAXA-x[i]][MAXA-y[i]];
ans = modAdd(ans,MOD-getC((x[i]+y[i])<<1,x[i]<<1));
}
rep(i,0,MAXA<<1) rep(j,0,MAXA<<1){
if(i) dp[i][j] = modAdd(dp[i][j],dp[i-1][j]);
if(j) dp[i][j] = modAdd(dp[i][j],dp[i][j-1]);
}
rep(i,1,n) ans = modAdd(ans,dp[x[i]+MAXA][y[i]+MAXA]);
printf("%lld\n",(llong(MOD+1)>>1)*ans%MOD);
return 0;
}