[Agc001E] BBQ Hard

题目大意

给定\(n\)对正整数\(a_i,b_i\)，求\(\sum_{i=1}^{n-1} \sum_{j=i+1}^n \binom{a_i+b_i+a_j+b_j}{a_i+a_j}\)。

试题分析

显然，后面的式子是一个\(\binom{n+m}{m}\)的形式，也就是我们从位置\((-a_i,-b_i)\)走到位置\((a_j,b_j)\)。

那么我们把式子转化成：$$\frac{\sum_{i=1}^n \sum_{j=1}^n \binom {a_i+b_i+a_j+b_j} {a_i+a_j} - \sum_{i=1}^n \binom{a_i+b_i+a_i+b_i}{a_i+b_i} }{2}$$

然后前面的可以直接dp，后面的直接算就好了。

#include<iostream>

#include<cstring>

#include<vector>

#include<queue>

#include<cstdio>

#include<algorithm>

using namespace std;

#define LL long long

inline int read(){

	int x=0,f=1;char c=getchar();

	for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;

	for(;isdigit(c);c=getchar()) x=x*10+c-'0';

	return x*f;

}

const int INF=9999999;

const int MAXN=300010;

const int MAXM=2010;

const int Mod = 1e9+7;

int N; int a[MAXN+1],b[MAXN+1];

int f[MAXM*2+1][MAXM*2+1];

LL ifac[MAXN+1],fac[MAXN+1],inv[MAXN+1];

int A[MAXN+1],B[MAXN+1];

inline LL C(LL n,LL m){

	if(n<m) return 0; if(n==m||!m) return 1;

	return fac[n]*ifac[m]%Mod*ifac[n-m]%Mod;

}

int main(){

	//freopen(".in","r",stdin);

	//freopen(".out","w",stdout);

	N=read(); fac[0]=1; inv[1]=1; ifac[1]=ifac[0]=1; LL ans=0;

	for(int i=1;i<=(MAXM<<2)+100;i++) fac[i]=fac[i-1]*i%Mod;

	for(int i=2;i<=(MAXM<<2)+100;i++){

		inv[i]=(Mod-(Mod/i))*inv[Mod%i]%Mod;

		ifac[i]=ifac[i-1]*inv[i]%Mod;

	}

	for(int i=1;i<=N;i++){

		A[i]=read(),B[i]=read();

		f[MAXM-A[i]][MAXM-B[i]]++;

		ans=(ans-C(A[i]*2+B[i]*2,A[i]*2)%Mod+Mod)%Mod;

	}

	for(int i=1;i<=MAXM*2;i++){

		for(int j=1;j<=MAXM*2;j++){

			(f[i][j]+=f[i-1][j])%=Mod;

			(f[i][j]+=f[i][j-1])%=Mod;

		}

	}

	for(int i=1;i<=N;i++){

		(ans+=f[A[i]+MAXM][B[i]+MAXM])%=Mod;

	} printf("%lld\n",ans*inv[2]%Mod);

	return 0;

}

[Agc001E] BBQ Hard的相关教程结束。