题解 P2119 【魔法阵】
施玮宸SECSA
·
·
题解
这道题是一个很好的数学题\
$O(n^4)$暴力枚举。\
$55$分\
为神马不排序呢~~~
------------
$100$分\
利用数学方法来做\
可以用桶先来排序\
再进行枚举a,d。\
代码~~~
```
#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[15001],b[15001],c[15001],d[15001];
int x[40001],s[15001];
int sum=0;
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
cin>>x[i];
s[x[i]]++;//桶
}
for(int i=1;i*9<n;i++){
sum=0;
for(int j=i*9+2;j<=n;j++){
sum+=s[j-9*i-1]*s[j-7*i-1];
d[j]+=sum*s[j-i];
c[j-i]+=sum*s[j];//d
}
sum=0;
for(int j=n-i*9-1;j>=1;j--){
sum+=s[j+8*i+1]*s[j+9*i+1];
b[j+2*i]+=sum*s[j];
a[j]+=sum*s[j+2*i];//a
}
}
for(int i=1;i<=m;i++){
cout<<a[x[i]]<<" ";
cout<<b[x[i]]<<" ";
cout<<c[x[i]]<<" ";
cout<<d[x[i]]<<" ";//输出
cout<<endl;
}
return 0;
}
```
再见！