CF1425D Danger of Mad Snakes题解

CF1425D Danger of Mad Snakes

题意：有一个$1000\ast 1000$的地图，上面有一些蛇，第i条蛇在$(x_i,y_i)$，每条蛇会有一个危险程度$a_i$。 有$m$个半径为$r$的对蛇攻击圈，对于每一种方案的贡献就是所有对蛇攻击圈中的所有蛇危险程度之和的平方，现要计算每一种方案贡献之和。 解法：看了半天才看懂官方题解，先单独考虑两条蛇$(i,j)$的贡献，这两条蛇的危险程度是$a_i,a_j$，对答案的贡献是以$(...+a_i+a_j+...{)}^2$这样的形式给出的，所以这两条蛇的贡献一定是$(a_i^2+a_j^2)\ast w_1+(2\ast a_i\ast a_j)\ast w_2$。对于$2\ast a_i\ast a_j$出现次数的话就需要用到容斥原理了。 定义以下三种情况：

W:导致i,j同时被杀的对蛇攻击圈数量U:导致i被杀，j不被杀的对蛇攻击圈数量V:导致j被杀，i不被杀的对蛇攻击圈数量

这些都能用二维前缀和处理出来，用bitset也可。

考虑以下两种情况：

一个对蛇攻击圈包含了i蛇和j蛇，这个数量就是随便取-不同时包含的数量，计算方法就是$c[n][m]-c[n-W][m]$。两个对蛇攻击圈分别包含了i蛇和j蛇，令$n^{\prime }=n-W$，这种情况的计算方法是$c[n^{\prime }][m]-c[n^{\prime }-U][m]-c[n^{\prime }-V][m]+c[n^{\prime }-U-V][m]$ 两种情况的和就是$2\ast a_i\ast a_j$的出现次数啦。 代码： #include <algorithm> #include <iostream> #include <cstring> #include <vector> #include <cstdio> #include <queue> #include <cmath> #include <set> #include <map> #include<bitset> #define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define _for(n,m,i) for (register int i = (n); i < (m); ++i) #define _rep(n,m,i) for (register int i = (n); i <= (m); ++i) #define lson rt<<1, l, mid #define rson rt<<1|1, mid+1, r #define PI acos(-1) #define eps 1e-9 #define rint register int #define F(x) ((x)/3+((x)%3==1?0:tb)) #define G(x) ((x)<tb?(x)*3+1:((x)-tb)*3+2) using namespace std; typedef long long LL; typedef pair<LL, int> pli; typedef pair<int, int> pii; typedef pair<double, int> pdi; typedef pair<LL, LL> pll; typedef pair<double, double> pdd; typedef map<int, int> mii; typedef map<char, int> mci; typedef map<string, int> msi; template<class T> void read(T &res) { int f = 1; res = 0; char c = getchar(); while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); } while(c >= '0' && c <= '9') { res = res * 10 + c - '0'; c = getchar(); } res *= f; } const int ne[8][2] = {1, 0, -1, 0, 0, 1, 0, -1, -1, -1, -1, 1, 1, -1, 1, 1}; const int INF = 0x3f3f3f3f; const int N = 2010; const LL Mod = 1e9+7; const int M = 1e6+10; int n, m, r; int x[N], y[N]; LL a[N], num[N]; bitset<N> b[N]; LL c[N][N]; void initc() { for(int i = 0; i <= n; ++i) { c[i][0] = c[i][i] = 1; for(int j = 1; j < i; ++j) c[i][j] = (c[i-1][j] + c[i-1][j-1]) % Mod; } } int main() { scanf("%d %d %d", &n, &m, &r); initc(); //打表出组合数 _rep(1, n, i) scanf("%d %d %lld", &x[i], &y[i], &a[i]); //用二进制的形式统计，b[i][j] = 1表示这两条蛇可以同框 _rep(1, n, i) _rep(1, n, j) if(max(abs(x[i]-x[j]), abs(y[i]-y[j])) <= r) b[i][j] = 1; LL ans = 0, w; //先计算ai^2出现次数 _rep(1, n, i) { w = b[i].count(); //w可以表示与i蛇同框的有多少个 num[i] = (c[n][m] - c[n-w][m] + Mod) % Mod; //ai出现次数 ans = (ans + num[i] * a[i] % Mod * a[i] % Mod) % Mod; //计算ai^2的价值 } //再计算2*ai*aj的出现次数 _rep(1, n, i) _rep(i+1, n, j) { w = (b[i]|b[j]).count(); //w可以表示与i同框数量以及与j同框数量的共有多少个 w = ((num[i]+num[j]-c[n][m]+c[n-w][m])%Mod + Mod) % Mod; //计算出ai*aj*2总共的次数 ans = (ans + w * a[i] % Mod * a[j] % Mod * 2 % Mod) % Mod; } printf("%lld\n", ans); return 0; }