题目传送门

分析:

题目的意思大概可以转化为,给你数字n,然后给你A B数组,然后询问

\sum_{i\not =j} \begin{pmatrix}
A_i +B_i+A_j+B_j \\
A_i +B_i
\end{pmatrix}

然后给出数据范围,n≤200000, A[i],B[i]≤2000
我们可以发现, A B的范围都很小,那么我们可以进行模型转化,我们把

\begin{pmatrix}
A_i +B_i+A_j+B_j \\
A_i +A_j
\end{pmatrix}

看成从(-A_i,-B_i)走到(A_j,B_j)的方案数,这个东西,我们直接直接暴力跑就好了…先把所有点向右上方位移到第一象限,假设我们直接从原点出发,那么走到(x,y)点的方案数就是(x-1,y)+(x,y-1)方案数的和…然后我们一开始就把所有的起点位置的值加1,然后跑一次,就可以求出所有起点到一个终点的方案数…最后要减去自己到自己的方案,再除以2….
(感谢Vexoben的指导)

代码:

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define P pair<int,int>
const LL inf = 0x3f3f3f3f;
const LL mod = 1e9+7;
const LL N = 4e3+10;
template <typename tp> inline void read(tp &x)
{
    x=0;char c=getchar();int f=0;
    for(;c>'9'||c<'0';f|=(c=='-'),c=getchar());
    for(;c<='9'&&c>='0';x=(x<<3)+(x<<1)+c-'0',c=getchar());
    if(f) x=-x;
}
LL n,a[200010],b[200010],ans;
LL fac[N*2],fav[N*2],inv[N*2];
void init()
{
    fac[0]=fav[0]=1;
    inv[1] = fac[1] = fav[1] = 1;
    for (int i = 2; i < N * 2; ++i) 
    {
        inv[i] = -mod / i * inv[mod % i] % mod + mod;
        fac[i] = fac[i - 1] * i % mod;
        fav[i] = fav[i - 1] * inv[i] % mod;
    }
}
inline LL C(int x, int y) 
{
    if (x < 0 || x < y) return 0;
    return fac[x] * fav[y] % mod * fav[x - y] % mod;
}
LL cost[N][N];
signed main()
{
    read(n);init();
    for(int i=1;i<=n;i++) read(a[i]),read(b[i]);
    for(int i=1;i<=n;i++) cost[-a[i]+2001][-b[i]+2001]++;
    for(int i=1;i<=4001;i++)
        for(int j=1;j<=4001;j++)
            (cost[i][j]+=(cost[i-1][j]+cost[i][j-1]))%=mod;
    //cout<<ans<<endl;
    for(int i=1;i<=n;i++) 
        ans=(ans+cost[a[i]+2001][b[i]+2001])%mod;
    //cout<<ans<<endl;
    for(int i=1;i<=n;i++)
        ans=(ans-C(a[i]*2+b[i]*2,a[i]*2)+mod)%mod;
    printf("%lld\n",(ans*(mod+1)/2%mod+mod)%mod);
    return 0;
}

Leave A Comment

发表评论

电子邮件地址不会被公开。 必填项已用*标注