[CF 1425d] danger of mad snakes

Topic link

The question ：

There is one $1000\times 1000$ Of the lattice . Yes $n$ The snake is in the square , Each snake tells you the coordinates in the grid $(X_i,Y_i)$ And a weight $B_i$.
Then choose any of them $m$ A snake , For each selected snake , It and all satisfaction $max(|X^{\prime }-X|,|Y^{\prime }-Y|)<=R$ Located at $(X^{\prime },Y^{\prime })$ All snakes will be killed .
For one of the options , Its weight is the square of the sum of the weights of all snakes killed in the selection .
Find the sum of the weights of all the selected methods .

Ideas ：

Consider the square of the sum of weights $(B_i+B_j+B_k{)}^2$, Let's take the square form apart and turn it into $B_i^2+B_j^2+B_k^2+2B_i{B}_j+2B_i{B}_k+2B_j{B}_k$.

Consider calculating a single square term $B_i^2$ The contribution of , The total number of times each snake is selected $\times B_i^2$.
Let's calculate Total cases $-$ The number of cases not selected That's it .

Consider calculating the multiplication of two terms $2B_i{B}_j$ The contribution of , Is the number of times both snakes are selected $\times 2B_i{B}_j$.
Let's excuse this , Calculation The number of cases where neither is selected +$i$ Number of cases selected +$j$ Number of cases selected - The total number of cases That's it .

Code ：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1000000007;

ll fpow(ll a,ll n)
{
    
    ll sum=1,base=a%mod;
    while(n!=0)
    {
    
        if(n%2)sum=sum*base%mod;
        base=base*base%mod;
        n/=2;
    }
    return sum;
}
ll inv(ll a)
{
    
    return fpow(a,mod-2);
}
ll jie[1000005],rjie[1000005];
void initJie(ll n)
{
    
    jie[0]=1;
    for(ll i=1;i<=n;i++)jie[i]=jie[i-1]*i%mod;
    for(ll i=0;i<=n;i++)rjie[i]=inv(jie[i]);
}
ll C(ll n,ll k)
{
    
    if(k>n)return 0;
    else return jie[n]*rjie[k]%mod*rjie[n-k]%mod;
}
ll n,m,r;
ll x[2005],y[2005],b[2005];
bitset<2005>num[2005],tmp;
ll get1(ll i)
{
    
    return (b[i]*b[i]%mod*(C(n,m)-C(n-num[i].count(),m))%mod+mod)%mod;
}
ll get2(ll i,ll j)
{
    
    tmp=num[i]|num[j];
    return 2*b[i]*b[j]%mod*(C(n-tmp.count(),m)+(C(n,m)-C(n-num[i].count(),m))-C(n-num[j].count(),m))%mod;
}

int main()
{
    
    initJie(100000);
    scanf("%lld%lld%lld",&n,&m,&r);
    for(ll i=1;i<=n;i++)
    {
    
        scanf("%lld%lld%lld",&x[i],&y[i],&b[i]);
    }
    for(ll i=1;i<=n;i++)
    {
    
        for(ll j=1;j<=n;j++)
        {
    
            if(max(abs(x[j]-x[i]),abs(y[j]-y[i]))<=r)
            {
    
                num[i].set(j);
             }
        }
    }
    ll ans=0;
    for(ll i=1;i<=n;i++)
    {
    
        ans=(ans+get1(i))%mod;
    }
    for(ll i=1;i<=n;i++)
    {
    
        for(ll j=i+1;j<=n;j++)
        {
    
            ans=(ans+get2(i,j))%mod;
        }
    }
    printf("%lld\n",(ans%mod+mod)%mod);
    return 0;
}