**今日主题：模拟赛** ## 1.魔法阵（[原题](https://www.luogu.com.cn/problem/P2119)）魔改这四个式子设$t=Xd-Xc$ 然后转换第二个式子得 $Xb-Xa=2t$ 再带入第三个式子 $2t<(Xc-Xb)/3$ 移项 $6t<(Xc-Xb)$ 再转换 $6t+k=Xc-Xb$ 此处的k为$Xc-Xb$和$6t$的差从上面可以发现 $$Xb-Xa=2t$$ $$Xc-Xb=6t+k$$ $$Xd-Xc=t$$ 然后遍历所有可能的$t$ 很明显，在这里 $t<(n-1)/9$ 枚举$Xd$（从$t*9+2$枚举到$N$）然后顺便得出$Xc=Xd-t$ 此处需要使用前缀和优化 Why? 因为如果有两组$Xa1,Xb1$和$Xa2,Xb2$ **如果$Xb2>Xb1$且$Xc-Xb2>6t+k$，那么$Xa1,Xb1$这一组一定是成立的，因为$Xc-Xb1$只会比$Xc-Xb2$大** 所以是可以使用$SumA*SumB$的前缀和来优化的再枚举$Xa$ (从$n-9*t-1$枚举到$1$）等等，**为什么要从大到小？？** 和上面同理，如果有两组$Xc1,Xd1$和$Xc2,Xd2$，**而且$Xc26t+k$,那么$Xc1,Xd1$也绝对是成立的，因为$Xc1-Xb$只会比$Xc2-Xb$大** 所以此处应该使用$SumC*SumD$的**后缀和**优化是不是觉得**后缀和**这个名字很鬼畜？~~俺也一样~~ 然后就可以顺利的写出代码了 ~~（谁说的）~~ ```cpp #include using namespace std; int n, m; int x[50010]; int vis[50010]; int a[50010], b[50010], c[50010], d[50010]; int main() { cin >> n >> m; for (int i = 1; i <= m; i++) { cin >> x[i]; vis[x[i]]++; } for (int t = 1; t * 9 < n; t++) { int sum = 0; for (int D = t * 9 + 2; D <= n; D++) { int A = D - t * 9 - 1; int B = A + t * 2; int C = D - t; sum += vis[A] * vis[B]; c[C] += sum * vis[D]; d[D] += sum * vis[C]; } sum = 0; for (int A = n - 9 * t - 1; A >= 1; A--) { int B = A + 2 * t; int C = B + 6 * t + 1; int D = C + t; sum += vis[C] * vis[D]; a[A] += sum * vis[B]; b[B] += sum * vis[A]; } } for (int i = 1; i <= m; i++) { cout << a[x[i]] << " " << b[x[i]] << " " << c[x[i]] << " " << d[x[i]] << endl; } return 0; } ``` ~~2题因为太难在中间被老师毙掉，所以不要问我为什么没有2题~~ ~~3题因为全员不会离散数学没有讲完~~