AT1983 BBQ Hard 解题报告

题意

求(sum_{i=1}^{n} sum_{j=i+1}^{n} dbinom{a_i+a_j}{a_i+b_i+a_j+b_j})

解法

考虑(dbinom{a_i+a_j}{a_i+b_i+a_j+b_j})的几何意义,由(dbinom{x}{x+y})的意义可知这等价于从((0, ; 0))走到((a_i+a_j,; b_i+b_j))的路径条数,即从((-a_i, ; -b_i))走到((a_j, ; b_j))的路径条数

对于路径条数,我们有dp: (dp(i,; j)=dp(i-1, ; j)+dp(i,; j-1)),在本题中由于值域较小可以使用,只需在起始时给每个((-a_i, ; -b_i))都加上1(作为起点)即可

正确性显然

代码

#include<iostream>
using namespace std;
#define int long long
const int Mod = 1e9+7 ;
const int mxn = 2e6 ;
const int N=200005, M=8000;
int frac[mxn+5], inv[mxn+5];
int dp[M/2+5][M/2+5], base=M/4+2;
int n, a[N], b[N];
int power(int a, int b){
	int res=1, car=a; 
	while(b){
		if(b&1) (res*=car)%=Mod;
		(car*=car)%=Mod;
		b>>=1;
	}
	return res;
}
void init(){
	frac[0]=1 ;
	for(int i=1;i<mxn;++i) (frac[i]=frac[i-1]*i)%=Mod ;
	inv[mxn-1] = power(frac[mxn-1], Mod-2);
	for(int i=mxn-2;i>0;--i) inv[i]=(inv[i+1]*(i+1))%Mod ;
	inv[0] = 1 ;
}
int C(int n, int k){
	return ((frac[n]*inv[k]%Mod)*inv[n-k])%Mod ;
}
long long ans = Mod ;
signed main(){
	init() ; cin>>n;
	for(int i=1;i<=n;++i) cin>>a[i]>>b[i], ++dp[base-a[i]][base-b[i]];
	for(int i=1;i<=M/2+2;++i) for(int j=1;j<=M/2+2;++j) (dp[i][j]+=(dp[i-1][j]+dp[i][j-1]))%=Mod;
	for(int i=1;i<=n;++i) (ans+=dp[a[i]+base][b[i]+base]), (ans-=C(2*a[i]+2*b[i], 2*a[i]))%=Mod ; (ans+=Mod)%=Mod ;
	cout<<(ans*power(2, Mod-2))%Mod<<endl ;
}