目录
显示
题目链接
https://www.luogu.com.cn/problem/P6187
题解
\(k=0\) 的情况是 trivial 的,不必多说。
我们先重点研究一下 \(k=1\) 的情况。
\(k=1\) 时,整个序列排成了一个环。稍微找一下规律就会发现,将最大的数排在中间,而将剩下的数按顺序一左一右排列最优。
接下来考虑更一般的情况。
容易发现,这种情况下整个序列被分为 \(\gcd(n,k)\) 个环,每个环包含 \(p=\frac{n}{\gcd(n,k)}\) 个元素。各个环之间按 \(k=1\) 的情况来,相互独立,互不干扰。
这种情况下,将序列排序后,\(a_1 \sim a_p\),\(a_{p+1} \sim a_{2p}\),\(\ldots\) 放在一个环里最优。
证明可以看 EI 的题解。
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; int n,m; long long a[200005],res[200005]; int gcd(int x,int y) { return y==0?x:gcd(y,x%y); } int main() { ios::sync_with_stdio(false); cin>>n>>m; for(int i=1;i<=n;i++) cin>>a[i]; sort(a+1,a+n+1); while(m--) { int k; cin>>k; int p=k!=0?n/gcd(n,k):0; if(res[p])cout<<res[p]<<endl; else if(k==0) { for(int i=1;i<=n;i++) res[0]+=a[i]*a[i]; cout<<res[0]<<endl; } else { for(int i=1;i<=n;i+=p) { for(int j=0;j<p-2;j++) res[p]+=a[i+j]*a[i+j+2]; res[p]+=a[i]*a[i+1]+a[i+p-1]*a[i+p-2]; } cout<<res[p]<<endl; } } return 0; }