题解 P6187 最小环

· · 题解

题目传送门

这一题可以说是一道没那么找规律的找规律了。

我会猜结论

很好证明，我们可以分类讨论一下：

假设我们从编号为 1 的个数开始，那么第二个就是 1+k，第 i 个就是 (ik)\bmod n+1，我们会发现这些数构成的集合 A=\{0,k,2k,3k,\dots,(n-1)k\} 在 \bmod n 的意义下时互不相同的，恰好循环一次。

而第 n+1 个数 nk\bmod n=0，恰好和第一个相同，

假设 d=\gcd(k,n)。

所以可知 A=\{0,k,2k,3k,\dots,(n-1)k\} 在 \bmod n 的意义下等同于 A'=\{0,k/d,2k/d.3k/d,\dots,(n-1)k/d\} 在 \bmod \frac nd 的意义下。

那么，根据刚才的结论，集合 A'_1=\{0,k/d,2k/d.3k/d,\dots,(\frac nd-1)k/d\} 互不相同，集合 A'_2=\{\frac ndk,(\frac nd+1)k/d,\dots,(2\frac nd-1)k/d\} 也互不相同。

总共刚好分成 \frac nd 组。

我会贪心

我们考虑反证法来证明。

假设上述方案不是最优解，那么肯定存在两个环，一个环中一个点 x 的贡献为 x\times(x_1+x_2)，另外一个环中一个点 y 的贡献为 y\times(y_1+y_2)。

并且满足 x>y\ \&\&\ x_1+x_2<y_1+y_1。

那么交换 x,y，会发现贡献是 yx_1+yx_2+xy_1+xy_2=xx_1+xx_2+xy_1+xy_2-(x-y)(x_1+x_2)。

很原来的贡献 =xx_1+xx_2+xy_1+xy_2-(x-y)(y_1+y_2)。

很明显，交换之后会更优。

也可以这样想：我们尽可能让大的和大的乘在一起，因此让最大的排在一个换里面。

我还会贪心

我们继续考虑一个环里如何分配是最优的。

我们的贪心思路还是这样：尽可能让大的和大的乘在一起。

因此，就有了这一张图：

（里面的数字表示它在这几个数的从大到小的排名）

我们先把最大的放在中间，为了保证与它乘的数尽量大，于是就把二和三放旁边。

剩下的最大的是第二大的数，为了保证与它乘的数尽量大，于是把第四大放在它旁边。

以此类推，就得到了上图。

严谨证明应该和结论二的方法差不多，用反证法应该可以证出来。

因此我们又可以得到一张图：

其实这样贡献就是隔一个乘一次，再把前两个的乘积和后两个的乘积加起来就行了。

好处：不需要额外处理环的长度只有 2 的情况。

注意：要特判 k=0 的情况。

code

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10;
int n,t,k,ans[N],a[N];
signed main(){
    scanf("%lld%lld",&n,&t);
    for(int i=1;i<=n;i++)scanf("%lld",&a[i]),ans[0]+=a[i]*a[i];
    sort(a+1,a+n+1);
    for(int d=1;d<=n;d++){
        if(n%d)continue;
        for(int l=1;l<=n;l+=d){
            int r=l+d-1;
            for(int j=r;j>=l+2;j--)ans[d]+=a[j]*a[j-2];
            ans[d]+=a[r]*a[r-1]+a[l]*a[l+1];
        }
    }
    for(;t--;){
        scanf("%lld",&k);
        printf("%lld\n",k?ans[n/__gcd(k,n)]:ans[0]);
    }
}