原翻译表述有误(如「半径」等描述,与原题意不符)且格式难看,请求更改如下:
有一个 1000×1000 的地图,地图上有 N 条互不重合的蛇,每条蛇有一个危险度。
现有 M(M≤N) 个边长为 2×R+1 的正方形,你可以选择 N 条蛇中不重复的 M 条并以它们作为 M 个正方形的中心。任何一条被任何一个正方形包含的蛇都会被杀死,这种方案的收益是被杀死的所有蛇的危险度之和的平方(而不是平方的和)。
现求所有选蛇方案下收益之和。模 109+7。
有一个 $1000\times 1000$ 的地图,地图上有 $N$ 条互不重合的蛇,每条蛇有一个危险度。
现有 $M(M\le N)$ 个边长为 $2\times R+1$ 的正方形,你可以选择 $N$ 条蛇中不重复的 $M$ 条并以它们作为 $M$ 个正方形的中心。任何一条被任何一个正方形包含的蛇都会被杀死,这种方案的收益是被杀死的所有蛇的危险度之和的平方(而不是平方的和)。
现求所有选蛇方案下收益之和。模 $10^9+7$。