【NOIP2016普及组】魔法阵
不是枚举暴力，也不是公式$\mathcal{O(1)}$，而是两者的有机结合。——通过数学推导减少了枚举量，满足时间复杂度要求。
很大程度上借鉴了Henry_y的博客，把一些地方改成了你能看懂的版本。
当我得到这个问题时，我遇到了暴力。因为取得了不错的成绩，我得了65分。具体操作如下：
记录和排序(可以通过对数组实现)，\(b\)可以从\(a 1\)枚举，\(c\)可以从\(b 1\)枚举，以此类推；
枚举\(b，c，d\)后，if立即判断是否满足\(x _ ax _ bx _ CX _ d \)；
枚举完\(c\)后，立即判断\(3(X_b-X_a)X_c-X_b\)，注意乘除。
似乎还有闲荡的空间。比如枚举\(a，b，c\)后，\(d\)已经确认，可以通过记录一些奇怪的东西来继续卡片。然而，暴力有时会结束。让我们看看正解。
反正是要列举的。让我们从三个公式开始，看看是否有任何属性。设\(X_d-X_c=t\)，则有\(X_b-X_a=2t，X_c-X_b6t\)。如果您制作\(X_c-X_b=6t k\)(组成剩余部分)，关系图如下：
枚举\(t\)自然就想到了，因为\(k\ge 1\)就足以保证\(1\le 9tn\)。枚举\(d\)以确定\(c\): \(c=d-t\)的位置。对于这组\(c，d\)，最大值\(a，b\)为\(d-9-1，d-7t-1\)。让\(cnt_x\)表示值\(x\)(即桶)的出现次数，那么这组解对答案的贡献就是\(CNT _ a \乘以cnt_b\)，乘法原理。
如果\(a，b\)较小，则必须为真(满足\(X_c-X-b6t\))。不难想到前缀和优化。每次C [C]=sum * CNT [d]，d [d]=sum，累加a \ (sum=\ sum _ {a \阿乐_ {max}，b \ le b _ {max}} CNT _ a \乘以CNT _ b \。很好。
计算\(a，b\)同样，将其更改为枚举\(a\)，向后运行，并记录后缀sum (\(cnt_c\times cnt_d\))。
以下是空调代码：
int main(){ 0
int n，m；读(n)，读(m)；
for(int I=1；I=m；i) read(x[i])，CNT[x[I]]；
for(int t=1，sumt * 9nt){ 0
sum=0；
for(int d=t * 9 ^ 2；d=n；d){
int a=d-t*9-1，b=d-t*7-1，c=d-t；
sum=CNT[a]* CNT[b]；//前缀和
C[c]=sum*cnt[d]，D[D]=sum * CNT[c]；//乘法原理，下同
}
sum=0；
for(int a=n-t * 9-1；a；-a){ 0
int b=a t*2，c=a t*8 1，d=a t * 9 1；
sum=CNT[c]* CNT[d]；//后缀和
A[a]=sum*cnt[b]，B[B]=sum * CNT[a]；
}
}
for(int I=1；I=m；I){ 0
写(A[x[i]])，PT，写(B[x[i]])，PT，
写(C[x[i]])，PT，写(D[x[i]])，EN；//注意ABCD的出现次数作为此时的值，而不是数字。
}
返回0；
}
THE END
内容来源网络，如有侵权，联系删除，本文地址：https://www.230890.com/zhan/81989.html