夏晓光(loveJY)的博客

NOIonline提高T3

这个真不毒瘤,其实60pts做法很容易想到,但是当时太菜了真不太会啊

我们不考虑DP,直接贪心吧

首先我们会发现一个规律,要想让这个答案最大,我们必须要让大的数旁边的数尽可能大

然后我们去考虑构造这个东西,一个不难发现的东西是我们可以把这个大环变成几个小环,然后小环直接互不干扰

也就是我们有gcd(n,k)个环...证明...考虑我们一个数,走回原来的位置是需要n/gcd(n,k)步的,所以我
们本质不同的环只有gcd(n.k)个

记p=n/gcd(n,k)

然后这个环问题我们可以这样安排:前1~p的我们可以放进第一个环,然后第p+1到2p放到第二个环里....

这样不难发现我们构造出的答案是最大的

因为$a<b<c<d,ad+bc<ab+cd$

如果您敏锐的发现答案只和p有关,那么我们就可以记忆化一下每个不同的p的答案,然后有些询问就可以直接查了

具体构造过程有一点小边界问题:

我们要这样构造:i+1,i+3,i+5,i+7,i+...,i+n-1,i+n,i+n-2,i+n-4......i+2,i

所以对于任何一个pos,我们在不超过边界的情况下首先有pos*(pos-2)*(pos+2)

其次在边界处我们有i,i+1和i+n,i+n-1的关系要处理

复杂度O(nd(n)),d其实是log^2级别所以可行?

code:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const int MAXN = 2e5 + 10;
ll a[MAXN], f[MAXN];
int n, m;
int gcd(int a, int b) {
	if(b == 0) return a;
	return gcd(b, a % b);
}

namespace fastIO {
#define BUF_SIZE (1<<19)
	static char buf[BUF_SIZE], *p1 = buf + BUF_SIZE, *pend = buf + BUF_SIZE;
	inline char nc() {
		if(p1 == pend) {
			p1 = buf;
			pend = buf + fread(buf, 1, BUF_SIZE, stdin);
		}
		return *p1++;
	}
	inline int read() {
		int x = 0;
		char s = nc();
		for(; !isdigit(s); s = nc());
		for(; isdigit(s); s = nc())x = (x << 1) + (x << 3) + s - '0';
		return x;
	}
}
using namespace fastIO;

int main() {
	// freopen("test.in", "r", stdin);
	n = read();
	m = read();
	for(int i = 1; i <= n; ++i)a[i] = read();
	sort(a + 1, a + n + 1);
	while(m--) {
		ll ans = 0;
		int k = read();
		if(k == 0 || n == 1) {
			for(int i = 1; i <= n; ++i)ans += a[i] * a[i];
			printf("%lld\n", ans);
			continue;
		}
		int t = gcd(n, k), p = n / t;//有p个环
		// puts("QWQ");
		if(f[p]) {
			printf("%lld\n", f[p]);
			continue;
		}
		for(int i = 1; i <= n; i += p) {
			for(int j = 0; j < p - 2; ++j) {
				ans += a[i + j] * a[i + j + 2];//枚举每个乘积..
			}
			ans += (a[i] * a[i + 1] + a[i + p - 1] * a[i + p - 2]);//加上边界
		}
		printf("%lld\n", ans);
		f[p] = ans;
	}
	return 0;
}