脚本宝典收集整理的这篇文章主要介绍了AT1983 [AGC001E] BBQ Hard（组合计数），脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。

题意

有 (n) 个数对 ((a_i,b_i))，求：

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

数据范围

(2 leq N leq 200000)。

(1leq a_i,b_i leq 2000)。

思路

预处理出阶层，直接枚举的时间复杂度为 (O(n^2))。显然需要更优的做法。

可以考虑题目要求的式子的几何意义，(C_{a_i+b_i+a_j+b_j}^{a_i+a_j}) 可以看成是从直角坐标系的原点 ((0,0))，只向上或向右走，走到 ((a_i+a_j,b_i+b_j)) 的方案数（因为只向上或向右走，需要走 (a_i+a_j+b_i+b_j) 步，而其中 (a_i+a_j) 步是要向右走的，枚举哪几步向右走就是这个公式）。

但是这样还是无法做到更优的复杂度。可以考虑进一步转化为从 ((-a_i,-b_i)) 走到 ((a_j,b_j)) 的方案数，含义不变。对于每一个终点 ((a_i,b_i))，都可以从所有的 ((-a_j,-b_j)) 走过来，可以直接 (O(max (a_i+a_j)^2)) dp 算出所有的答案（具体实现可以看代码）。这样计算会多算 (i geq j) 的方案，于是可以先减去从 ((-a_i,-b_i)) 走到 ((a_i,b_i)) 的方案数，最终再把答案除以 (2) （乘以 (2) 的逆元）。

最终的时间复杂度就是 (O(n+4000^2))。

code：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int mod=1e9+7;
const int N=4040,NLC=2020,M=2e5+10;
int f[N][N],ans,n,inv[N<<1],fac[N<<1],infac[N<<1],a[M],b[M];
void init()
{
	fac[0]=fac[1]=inv[0]=inv[1]=infac[0]=infac[1]=1;
	for(int i=2;i<N<<1;i++)
	{
		fac[i]=1ll*fac[i-1]*i%mod;
		inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
		infac[i]=1ll*infac[i-1]*inv[i]%mod;
	}
}
int C(int n,int m){return 1ll*fac[n]*infac[m]%mod*infac[n-m]%mod;}
int main()
{
	init();
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d%d",&a[i],&b[i]),f[NLC-a[i]][NLC-b[i]]++;//直接储存负数会 RE，需要整体加上一个偏移量
	for(int i=1;i<N;i++)
	    for(int j=1;j<N;j++)
	        f[i][j]=(f[i][j]+f[i][j-1]+f[i-1][j])%mod;
	for(int i=1;i<=n;i++)
	{
		ans=(ans+f[NLC+a[i]][NLC+b[i]])%mod;
		ans=((ans-C(2*a[i]+2*b[i],2*a[i]))%mod+mod)%mod;
	}
	printf("%dn",1ll*ans*inv[2]%mod);
	return 0;
}

脚本宝典总结

以上是脚本宝典为你收集整理的AT1983 [AGC001E] BBQ Hard（组合计数）全部内容，希望文章能够帮你解决AT1983 [AGC001E] BBQ Hard（组合计数）所遇到的问题。

如果觉得脚本宝典网站内容还不错，欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。