【JZOJ 5358】【NOIP2017提高A组模拟9.12】BBQ

Description

给出序列a,b，求
∑i=1n∑j=1i−1Cai+ajai+aj+bi+bj
ans%=1e9+7
n,m<=100000,  ai,bi<=2000

Solution

看到C公式，应该就要想到在网格上Dp走，
这题就是这样，
相当从每个 (−ai,−bi) 走到每个 (aj,bj)
这个随便DP嘛

复杂度： o(20002)

Code

#include <cstdio>
#include <algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fod(i,a,b) for(int i=a;i>=b;i--)
#define min(q,w) ((q)>(w)?(w):(q))
#define max(q,w) ((q)<(w)?(w):(q))
using namespace std;
typedef long long LL;
const int N=4050,mo=1e9+7;
int read(int &n)
{
    char ch=' ';int q=0,w=1;
for(;(ch!='-')&&((ch<'0')||(ch>'9'));ch=getchar());
if(ch=='-')w=-1,ch=getchar();
for(;ch>='0' && ch<='9';ch=getchar())q=q*10+ch-48;n=q*w;return n;
}
int n,m1,m2;
int a[N*50][2];
LL ans;
LL f[N][N];
LL jc[N*2],jcn[N*2];
LL C(int n,int m){return jc[m]*jcn[n]%mo*jcn[m-n]%mo;}
LL ksm(LL q,int w)
{
    LL ans=1;
for(;w;w>>=1,q=q*q%mo)if(w&1)ans=ans*q%mo;
return ans;
}
int main()
{
read(n);
    fo(i,1,n)read(a[i][0]),read(a[i][1]),m1=max(m1,a[i][0]),m2=max(m2,a[i][1]);
    fo(i,1,n)f[m1-a[i][0]][m2-a[i][1]]++;
    jc[0]=1;
    fo(i,1,m1*2+m2*2)jc[i]=jc[i-1]*(LL)i%mo;
    jcn[m1*2+m2*2]=ksm(jc[m1*2+m2*2],mo-2);
    fod(i,m1*2+m2*2-1,0)jcn[i]=jcn[i+1]*(LL)(i+1LL)%mo;
    fo(i,0,m1*2)fo(j,0,m2*2)
    {
if(i)f[i][j]=f[i][j]+f[i-1][j];
if(j)f[i][j]=(f[i][j]+f[i][j-1])%mo;
    }
    ans=0;
    fo(i,1,n)ans=(ans+f[a[i][0]+m1][a[i][1]+m2]-C(a[i][0]*2,a[i][0]*2+a[i][1]*2))%mo;
    ans=ans*(500000004LL)%mo;
printf("%lld\n",(ans+mo)%mo);
return 0;
}