[agc001e]BBQ hard
发布时间：2020-12-14 03:45:14 所属栏目：大数据 来源：网络整理
导读：题意： 就是求$sumlimits_{i=1}^{n}sumlimits_{j=1}^{n}binom{a_i+b_i+a_j+b_j}{a_i+b_i}$ $1leq nleq 200000$ $1leq a_i,b_ileq 2000$ 题解： 这种题数据范围一看就是预处理答案，但是直接把和加起来的话复杂度依然是$n^2$的； 类似骗我呢那道题，
题意：就是求$sumlimits_{i=1}^{n}sumlimits_{j=1}^{n}binom{a_i+b_i+a_j+b_j}{a_i+b_i}$ $1leq nleq 200000$ $1leq a_i,b_ileq 2000$ 题解：这种题数据范围一看就是预处理答案，但是直接把和加起来的话复杂度依然是$n^2$的； 类似骗我呢那道题，可以考虑把组合数看成路径，那么上面的式子意思就是只能向右或向上走，从$(-a_i,-b_i)$走到$(a_j,b_j)$的方案数； 因为$a_i,b_i$都很小，所以可以直接dp出总的方案数： $f[i][j]=f[i-1][j]+f[i][j-1]$ 初始化时把$(-a_i,-b_i)$设为1即可； 统计答案时记得减去自己走到自己的方案数！ 为了计算方便，我把所有坐标向右上平移了2000个单位。 1 #include<algorithm>
2 #include<iostream>
3 #include<cstring>
4 #include<cmath>
5 #define mod 1000000007
6 #define inv_2 500000004
7 using namespace std; 8 typedef long long ll; 9 ll n,ans=0,a[200001],b[200001],f[4010][4010],inv[10001],jc[10001]; 10 ll fastpow(ll x,ll y){ 11 int ret=1; 12 for(;y;y>>=1,x=(ll)x*x%mod){ 13 if(y&1)ret=(ll)ret*x%mod; 14 } 15 return ret; 16 } 17 void _(){ 18 jc[0]=1; 19 for(int i=1;i<=10000;i++)jc[i]=(ll)jc[i-1]*i%mod; 20 inv[10000]=fastpow(jc[10000],mod-2); 21 for(int i=9999;i;i--)inv[i]=(ll)(i+1)*inv[i+1]%mod; 22 inv[0]=1; 23 } 24 int C(int n,int m){ 25 return (ll)jc[n]*inv[m]%mod*inv[n-m]%mod; 26 } 27 int main(){ 28 _(); 29 memset(f,0,sizeof(f)); 30 scanf("%d",&n); 31 for(int i=1;i<=n;i++){ 32 scanf("%d%d",&a[i],&b[i]); 33 f[-a[i]+2001][-b[i]+2001]++; 34 } 35 for(int i=1;i<=4001;i++){ 36 for(int j=1;j<=4001;j++){ 37 f[i][j]=(f[i][j]+f[i][j-1]+f[i-1][j])%mod; 38 } 39 } 40 for(int i=1;i<=n;i++){ 41 ans=(ans+f[a[i]+2001][b[i]+2001])%mod; 42 } 43 for(int i=1;i<=n;i++){ 44 ans=(ans-C(a[i]*2+b[i]*2,a[i]*2)+mod)%mod; 45 } 46 //ans=ans/2%mod;
47 ans=(ll)ans*inv_2%mod; 48 printf("%dn",ans); 49 return 0; 50 }
（编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |