P6300 悔改。

这道题标签没有生成函数，但是这个就是生成函数的题，算模板吧。

这种题先设 cic_i 表示 ii 的出现次数。

ansk=12∑i+j=kmin⁡(ci,cj)=12∑d=1n∑i+j=k[ci≥d][cj≥d]\begin{aligned} ans_k &= \frac{1}{2} \sum_{i+j=k}\min(c_i,c_j)\\ &=\frac{1}{2} \sum_{d=1}^n\sum_{i+j=k}[c_i\ge d][c_j\ge d]\\ \end{aligned}

我们发现这个很像生成函数的卷积形式，于是我们设生成函数 fd(x)f_d(x)：

fd(x)=∑i[ci≥d]xif_d(x)=\sum_i [c_i\ge d]x^i

然后将 fd(x)f_d(x) 代入：

ansk=12∑d=1nfd(x)2(k)ans_k=\frac{1}{2}\sum_{d=1}^nf_d(x)^2(k)

到现在我们已经推完了生成函数，但是这个还是会 TLE。我们还需要一点注意力，可以发现，dd 离散化之后就是 O(n)O(\sqrt n) 级别的了。

然后上面的卷积就用 FFT/NTT 求出来即可，时间复杂度 O(mnlog⁡m)O(m\sqrt n \log m)。

C++
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=998244353,g=3;
const int pi=acos(-1);
int n,m,T,t[400010],l,lm=1,r[400010];
int d[400010],c[400010];

int a[400010],b[400010];
int ksm(int a,int b){
	int res=1;
	while(b){
		if(b&1)res=res*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return res;
}

void NTT(int *A,int t){
	for(int i=0;i<lm;i++)if(i<r[i])swap(A[i],A[r[i]]);
	for(int mid=1;mid<lm;mid<<=1){
		int wn=ksm(g,(mod-1)/(mid<<1));
		if(t==-1) wn=ksm(wn,mod-2);
		int d=wn;
		int R=mid*2;
		for(int j=0;j<lm;j+=R){
			int w=1;
			for(int k=0;k<mid;k++,w=w*d%mod){
				int x=A[j+k],y=w*A[j+mid+k]%mod;
				A[j+k]=(x+y)%mod,A[j+mid+k]=(x-y+mod)%mod;
			} 
		}
	}
	if(t==-1){
		int inv=ksm(lm,mod-2);
		for(int i=0;i<lm;i++)A[i]=A[i]*inv%mod;
	}
}
void mul(int *A,int *B){
	NTT(A,1),NTT(B,1);
	for(int i=0;i<lm;i++)A[i]=A[i]*B[i]%mod;
	NTT(A,-1);
	//a
}
int ans[400010];
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>t[i],c[t[i]]++;
	while(lm<=m*2)l++,lm<<=1;
	for(int i=0;i<lm;i++)r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
	for(int i=1;i<=m;i++)if(c[i])d[++T]=c[i];
	sort(d+1,d+T+1);
	T=unique(d+1,d+T+1)-d-1;
	for(int p=1;p<=T;p++){
		for(int i=0;i<=m;i++)b[i]=a[i]=(c[i]>=d[p]);
		for(int i=m+1;i<lm;i++)a[i]=b[i]=0;
		mul(a,b);
		for(int j=2;j<=m*2;j++)ans[j]+=(d[p]-d[p-1])*a[j];
	}
	int id=0;
	for(int i=2;i<=m*2;i++)if(ans[i]>ans[id])id=i;
	cout<<ans[id]/2<<' '<<id<<endl;
	return 0;
}
/*

*/