[计数 DP]Atcoder AGC001 E. BBQ Hard

2019-04-14 08:58发布

站内文章 / 模拟电子
9614 0 937
答案是求 ∑i≠j(ai+aj+bi+bjai+aj) 这就相当于从平面内的 (−ai,−bi) 走到 (aj,bj) 的方案数 把点放到平面上，DP就好了 #include #include #include using namespace std; const int N=8010,P=1e9+7; int n,a[200010],b[200010],fac[N],inv[N]; int f[N][N]; inline int &F(int x,int y){ return f[x+2005][y+2005]; } inline void Pre(){ fac[0]=1; for(int i=1;i<=8000;i++) fac[i]=1LL*fac[i-1]*i%P; inv[1]=1; for(int i=2;i<=8000;i++) inv[i]=1LL*(P-P/i)*inv[P%i]%P; inv[0]=1; for(int i=1;i<=8000;i++) inv[i]=1LL*inv[i]*inv[i-1]%P; } inline int C(int x,int y){ return 1LL*fac[x]*inv[y]%P*inv[x-y]%P; } int main(){ freopen("1.in","r",stdin); freopen("1.out","w",stdout); scanf("%d",&n); Pre(); for(int i=1;i<=n;i++) scanf("%d%d",&a[i],&b[i]),F(-a[i],-b[i])++; for(int i=-2000;i<=2000;i++) for(int j=-2000;j<=2000;j++) F(i,j)=((long long)F(i,j)+F(i-1,j)+F(i,j-1))%P; int ans=0; for(int i=1;i<=n;i++) ans=((long long)ans+F(a[i],b[i])-C(a[i]+a[i]+b[i]+b[i],b[i]+b[i]))%P; ans=1LL*ans*(P+1>>1)%P; printf("%d ",(ans+P)%P); return 0; }

热门文章