(k=0)请自行特判
对于一个(k),我们给所有(i)连边((i,(i+k-1)mod n+1)),这样就会形成(gcd(n,k))个环,每个环长度为(frac{n}{gcd(n,k)}),那么我们就是要把数放在环上,使得所有相邻两个数的乘积的和最大.这里有两个结论:
- 对于一个环,把环内的数从大到小排序,然后依次放入,放的时候要使得放过的数是连续的一段,并且接下来放进来的数要放在连续段更大的端点旁边
一般的,考虑一个乱序的环,然后通过交换一些数的位置增量模拟上述过程.后面有(age bge cge d),(bge e),且(a,b,c)三数的大小排名相邻.假设我们现在已经放好了段([a...b]),接下来一个要放的数为(c),相当于有(cdots e,c,cdots d,a,cdots b,cdots)(这里可能会出现(d,e)就是(b)或(c)的情况,但是不影响证明),那么我们把([c,d])段整体翻转,可以发现答案的变化量为(ac+de-ad-ce=a(c-d)+e(d-c)=(a-e)(c-d)),因为(age e,cge d),所以可以推出答案变化量不小于(0).那么这样一直做到不能做就可以得到最优解
- 把数从小到大排序,那么前(frac{n}{gcd(n,k)})个数会放在一个环内,接下来(frac{n}{gcd(n,k)})个数会放在一个环内...依此类推
否则,我们每次找到两个环,记最小值更小的环为(A)环,另外一个为(B)环,然后假设满足(A)环的前(x)大的数(ge B)环前(x)小的数,那么现在把这些数分别换到另一个环里.我们先把两个环的元素按照环内排序的方法排序,然后对应要换的(x)个数在两个环上都是连续一段,且换到另一个环上后会变成(A)环最大的(x)个或是(B)环最小的(x)个.那么考虑再答案的变化量,设(A)环上被换出的段为([a...b]),在环上的情况为(cdots c,acdots b,dcdots),设(B)环上被换出的段为([e...f]),在环上的情况为(cdots g,ecdots f,hcdots),这里显然有(age e,bge f,cle g,dle h),那么写出交换后答案变化量(ag+bh+ec+fd-ac-bd-eg-fh=a(g-c)+b(h-d)+e(c-g)+f(d-h)=(a-e)(g-c)+(b-f)(h-d)),同样的这个变化量(ge 0).一直这样做可以发现答案一定不减,做到做不了就是最优解了
所以确定了一个(k),可以按照上述方法去放,就是(O(n))的.由于可以(gcd(n,k))数量只有(O(d(n)))中,所以处理出每种(gcd(n,k))的答案即可,复杂度(O(nd(n))),可以通过