题解：P2119 [NOIP 2016 普及组] 魔法阵
Qfaiser
·
·
题解
solution
一道数学推导优化枚举的题。
容易写出暴力枚举，考虑通过缩小枚举范围优化枚举。
知道 X_a<X_b<X_c<X_d 且 X_b-X_a=2(X_d-X_c)<(X_c-X_b) \div 3。
设一个参数 k=X_d-X_c，对原式变形得 X_b-X_a=2k 和 6k<X_c-X_b，即 X_b=X_a+2k 和 X_c>X_b+6k。
对于每个 k，X_a 到 X_b、X_c 到 X_d 的距离都是定值，而 X_b 到 X_c 的距离是个区间。
首先要了解这点。若 X_{c_1}<X_{c_2} 且X_{d_1}<X_{d_2}，并且 X_{c_1}-X_b > 6k，即 X_{c_1} 和 X_{d_1} 可以组成魔法阵，那么 X_{c_2}-X_b > 6k，也就是 X_{c_2} 和 X_{d_2} 一定可以组成魔法阵。
类似的，若 X_{a_1}<X_{a_2} 且X_{b_1}<X_{b_2}，并且 X_c-X_{b_2} > 6k，即 X_{a_1} 和 X_{b_1} 可以组成魔法阵，那么 X_c-X_{b_1} > 6k，也就是 X_{a_2} 和 X_{b_2} 一定可以组成魔法阵。
我们从后往前枚举 X_a，记 S_{x_i} 表示 x_i 出现次数，乘法原理得当前可以作为 X_a 的个数为 S_{X_b} \times S_{X_c} \times S_{X_d}，用一个后缀和维护 S_{X_c} \times S_{X_d} 变枚举边算，这样就可以 O(n^2) 做了。
从前往后枚举 X_d，维护前缀和，同样可以算出贡献。
那就得到了做法，先枚举 k，再分别枚举 X_a 和 X_d 的范围计算贡献。
$X_d$ 的范围是 $9k+2$ 到 $n$。当 $y=1$ 且 $X_a=1$ 时 $X_d$ 最小。
这道题还是有点抽象，不太好描述，可以结合代码体会。
## code
```cpp
#include <bits/stdc++.h>
using namespace std;
int n, m, A[50005][4], x[50005], num[50005];
int main () {
cin >> n >> m;
for (int i=1; i<=m; ++i)
cin >> x[i],
num[x[i]]++;
for (int k=1, a, b, c, d, s; 9*k<=n; ++k) {
for (a=n-9*k-1, s=0; a>=1; --a) // 枚举a，确定bcd
b=a+2*k, c=b+6*k+1, d=c+k,
s+=num[c]*num[d],
A[a][0]+=num[b]*s,
A[b][1]+=num[a]*s;
for (d=9*k+2, s=0; d<=n; ++d) // 枚举d，确定abc
a=d-9*k-1, b=a+2*k, c=d-k,
s+=num[a]*num[b],
A[c][2]+=num[d]*s,
A[d][3]+=num[c]*s;
}
for (int i=1; i<=m; ++i, cout << '\n')
for (int j=0; j<4; ++j)
cout << A[x[i]][j] << ' ';
return 0;
}
```