赛时

赛时代码时间复杂度是错的，所以就不过多阐述只是分享一下赛时的思路。

根据琴生不等式或感性理解，在赛时我的结论是，优先选择 $L$ 在剩下余数分配时应当选择更大的组，例如如果分成 $3,3,4,4$ 不如分成 $3,3,3,5$ 所以写出了又臭又长结论复杂的代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll N=5e5+5,M=730,mod=1e9+7;
ll n,q,a[N],pre[N],len,inv[N];
map<pair<ll,ll>,ll> mp;
vector<ll> zw[N];
ll ksm(ll a,ll b){
	ll res=1;a%=mod;
	while(b){
		if(b&1) res=res*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return res;
}
signed main(){
	ios::sync_with_stdio(0),cout.tie(0),cin.tie(0);
	cin>>n>>q;len=n;
	for(int i=1;i<=n;i++) cin>>a[i];
	sort(a+1,a+1+n,greater<ll>());
	for(int i=1;i<=n;i++) pre[i]=(pre[i-1]+a[i])%mod;
	for(ll i=1;i<=n;i++) inv[i]=ksm(i*i,mod-2);
	for(int i=1;i<=n;i++){
		zw[i].push_back(0);
		ll tmp=0;
		for(int j=1;j+i-1<=n;j+=i){
			ll t=(pre[j+i-1]-pre[j-1]+mod)%mod;
			tmp=(tmp+t*t%mod*inv[i]%mod)%mod;
			zw[i].push_back(tmp);
		}
	}
	while(q--){
		ll l,r;cin>>l>>r;
		if((n+r-1)/r>n/l) cout<<"-1\n";//判断无解
		else{
			r=min(r,l*2);
			if(mp.count({l,r})){cout<<mp[{l,r}]<<"\n";continue;}
			ll t=n%l;
			vector<ll> G;
			for(ll i=min(r-l,l-1);;){
				if(t==0) break;
				while(t>=i){
					G.push_back(i+l);
					t-=i;
				}
				i=min(t,i);
			}
			t=n/l-G.size();
			ll ans=zw[l][t],it=G.size()-1;
			for(int i=t*l+1;;){
				if(it<=-1) break;
				ll tmp=(pre[i+G[it]-1]-pre[i-1]+mod)%mod;
				ans=(ans+tmp*tmp%mod*inv[G[it]]%mod)%mod;
				i+=G[it];
				it--;
			}
			mp[{l,r}]=ans;
			cout<<ans<<"\n";
		}
	}
	return 0;
}

先预处理出长度为 $i$ 的块从头到尾选 $j$ 组的答案，再将余数分配到若干组长度为 $L$ 的块中。

根据根号分治的思想，如果 $L$ 大于 $\sqrt n$ 则他分成的组数不会大于 $\sqrt n$，如果 $L$ 小于 $\sqrt n$ 则就算余数为 $L-1$，前面已经判断过无解所以这时候 $L \lt R$ 最多分配到 $L-1$ 组内，综合时间复杂度为 $O(n \log n + q \sqrt n)$ 这显然是过不了这题的。

但是话又说回来，因为数据出的太水了加了个记忆化就过了，最后五秒才过，我太菜了。

if(mp.count({l,r})){cout<<mp[{l,r}]<<"\n";continue;}

记忆化神力。。。

正解

在听讲解时，讲到这题的时候我以为至少会讲一会，没想到居然跟最后一题一样直接秒过去了。

官方给出了三个结论，官方证明放结尾了带大家感性理解一下这几个性质。

结论一：存在一组取到最大值的方案，使得每一个组构成一段连续的区间。

这确实很好理解，可以将题目所求理解成平均数的平方，所以越接近的那些数组成一组一定最大。

结论二：存在一种取到最大值的方案，使得每一个组划分构成连续区间，且当给出的区间限制为 $[l,r]$ 时，区间长度序列 $l_1,l_2 \ldots l_t$ 的结构形如 $r^A x l^B$ ($s^k$ 表示 $s$ 重复 $k$ 次)

这是为什么呢？我们知道如果选择越多的 $L$ 则越优。

1. $R - L \geq N \% L$ 则可以直接选择若干个 $L$ 与一个 $L + N \% L$ 这样一定是最优的。
2. $R - L \lt N \% L$ 则可以使用调整法将序列长度命名为 $len_1,len_2 \ldots len_k$ ($L \leq len_i \leq R,len_1 \leq len_2 \leq \ldots \leq len_k$) 每个长度 $len_i$ 组的和为 $s_i$。原先两个块对答案的贡献为 $\frac{s_x^2}{len_x^2} + \frac{s_{x+1}^2}{len_{x+1}^2}$，现在将 $x+1$ 组的第一个删除放到 $x$ 组中则 $\frac{s_x}{len_x} \leq a \leq \frac{s_{x+1}}{len_{x+1}}$ 因为我们可以理解成平均数的平方所以将 $a$ 元素放到 $x$ 组中这样一定是不降的，最终也有可能会有一个元素无法转移，所以这样整个长度序列的结构就形如 $r^A x l^B$。

结论三: 存在一种取到最大值的方案，其满足结论二，且为满足结论二中 $r^A x l^B$ 中 $A$ 最小的方案，若有多个满足 $A$ 最小，则选择其中 $B$ 最大的方案。

因为现在我们知道结构一定是 $r^A x l^B$，所以直接考虑 $R - L \lt N \% L$ 的情况，如果我们选择多的 $R$ 则我们可以取出若干个 $R - L$ 拼凑成一个 $L$ 因为可以理解为平均数的平方这样会多出来一个平均数且大于原先的块的答案所以一定更优。

代码如下：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll N=5e5+5,M=730,mod=1e9+7;
ll n,q,a[N],pre[N],len,inv[N];
map<pair<ll,ll>,ll> mp;
vector<ll> zw[N],wz[N];
ll ksm(ll a,ll b){
	ll res=1;a%=mod;
	while(b){
		if(b&1) res=res*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return res;
}
signed main(){
	ios::sync_with_stdio(0),cout.tie(0),cin.tie(0);
	cin>>n>>q;len=n;
	for(int i=1;i<=n;i++) cin>>a[i];
	sort(a+1,a+1+n,greater<ll>());
	for(int i=1;i<=n;i++) pre[i]=(pre[i-1]+a[i])%mod;
	for(ll i=1;i<=n;i++) inv[i]=ksm(i*i,mod-2);
	for(int i=1;i<=n;i++){
		ll tmp=0;zw[i].push_back(0);
		for(int j=1;j+i-1<=n;j+=i){
			ll t=(pre[j+i-1]-pre[j-1]+mod)%mod;
			tmp=(tmp+t*t%mod*inv[i]%mod)%mod;
			zw[i].push_back(tmp);
		}
		tmp=0;wz[i].push_back(0);
		for(int j=n;j-i+1>=1;j-=i){
			ll t=(pre[j]-pre[j-i]+mod)%mod;
			tmp=(tmp+t*t%mod*inv[i]%mod)%mod;
			wz[i].push_back(tmp);
		}
	}
	while(q--){
		ll l,r;
		cin>>l>>r;
		if((n+r-1)/r>n/l) cout<<"-1\n";
		else{
			ll t=n%l,cnt=n/l;
			if(r-l>=t){
				cnt--;
				ll ans=zw[l][cnt];
				ll tmp=(pre[n]-pre[cnt*l]+mod)%mod;
				ans=(ans+tmp*tmp%mod*inv[t+l]%mod)%mod;
				cout<<ans<<"\n";
			}else{
				ll cc=t/(r-l);
				if(t%(r-l)==0){
					ll ans=(zw[l][cnt-cc]+wz[r][cc])%mod;
					cout<<ans<<"\n";
				}else{
					cnt=cnt-cc-1;
					ll ans=(zw[l][cnt]+wz[r][cc])%mod;
					ll t1=cnt*l+1,t2=n-cc*r;
					ll tmp=(pre[t2]-pre[t1-1]+mod)%mod;
					ans=(ans+tmp*tmp%mod*inv[t2-t1+1]%mod)%mod;
					cout<<ans<<"\n";
				}
			}
		}
	}
	return 0;
}

跑的跟记忆化差不多，时间复杂度 $O(n \log n + q)$。

官方证明如下：