题目概述

CF1425D

解题报告

把和的平方拆开：

$$ (\sum_{i=1}^{m}B_i)^2=\sum_{i=1}^{m}B_i^2+\sum_{i=1}^{m-1}\sum_{j=i+1}^{m}2B_iB_j $$

我们分别统计两块的贡献，令 $S_i$ 表示以蛇 $i$ 为中心的正方形中的蛇。

对于 $i$ ，只要 $S_i$ 中的蛇被选了，$i$ 就有一次 $B_i^2$ 的贡献，容斥一下可以得出方案数为 ${n\choose m}-{n-S_i\choose m}$ 。

对于 $i<j$ ，只要 $S_i$ 和 $S_j$ 中都有蛇被选，$i$ 和 $j$ 就有一次 $2B_iB_j$ 的贡献。

假设 $S_i$ 和 $S_j$ 的交集为 $T$ ，我们还是考虑容斥，设 $i$ 被覆盖、$j$ 没被覆盖的方案数为 $A$ ，$j$ 被覆盖、$i$ 没被覆盖的方案数为 $B$ ，$i,j$ 都被覆盖的方案数为 $C$ ，$i,j$ 都被没覆盖的方案数为 $D$ ：

$$ \begin{cases} A+B+C+D={n\choose m}\\ A+D={S_i+T\choose m}\\ B+D={S_j+T\choose m}\\ D={n-S_i-S_j-T\choose m} \end{cases} $$

这样就可以得到方案数 $C={n\choose m}-{S_i+T\choose m}-{S_j+T\choose m}+{n-S_i-S_j-T\choose m}$ 。

求交集的话还是利用容斥（真tm全是容斥）。

示例程序

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=2000,maxl=1000,MOD=1e9+7;
 
int n,m,R,X[maxn+5],Y[maxn+5],w[maxn+5],sum[maxl+5][maxl+5];
int S[maxn+5],C[maxn+5][maxn+5],ans;
 
inline int abs(int x) {return x<0?-x:x;}
inline bool check(int i,int j) {return max(abs(X[i]-X[j]),abs(Y[i]-Y[j]))<=R;}
#define ADD(x,y) (((x)+(y))%MOD)
#define MUL(x,y) ((LL)(x)*(y)%MOD)
int Count(int i,int j){
    int A=max(X[i]-R,X[j]-R),B=min(X[i]+R,X[j]+R);
    int C=max(Y[i]-R,Y[j]-R),D=min(Y[i]+R,Y[j]+R);
    if (A<1) A=1;if (B>maxl) B=maxl;
    if (C<1) C=1;if (D>maxl) D=maxl;
    if (A>B || C>D) return 0;
    return sum[B][D]-sum[A-1][D]-sum[B][C-1]+sum[A-1][C-1];
}
int main(){
    scanf("%d%d%d",&n,&m,&R);
    for (int i=1;i<=n;i++) scanf("%d%d%d",&X[i],&Y[i],&w[i]),sum[X[i]][Y[i]]++;
    for (int i=1;i<=maxl;i++) for (int j=1;j<=maxl;j++) sum[i][j]+=sum[i][j-1];
    for (int i=1;i<=maxl;i++) for (int j=1;j<=maxl;j++) sum[i][j]+=sum[i-1][j];
    for (int i=0;i<=n;i++) C[i][0]=1;
    for (int i=1;i<=n;i++) for (int j=1;j<=i;j++) C[i][j]=ADD(C[i-1][j-1],C[i-1][j]);
    for (int i=1;i<=n;i++){
        for (int j=1;j<=n;j++) S[i]+=check(i,j);
        int cnt=ADD(C[n][m],MOD-C[n-S[i]][m]);
        ans=ADD(ans,MUL(cnt,MUL(w[i],w[i])));
    }
    for (int i=1;i<n;i++)
        for (int j=i+1;j<=n;j++){
            int T=Count(i,j),A=S[i]-T,B=S[j]-T,N=n-(A+B+T);
            int cnt=ADD(C[n][m],C[N][m]);
            cnt=ADD(cnt,MOD-ADD(C[A+N][m],C[B+N][m]));
            ans=ADD(ans,MUL(cnt<<1,MUL(w[i],w[j])));
        }
    printf("%d\n",ans);return 0;
}