题目
给出两个等长的序列(a,b)，
重排序列(b)，使得(a+b)众数出现的次数最多
分析
设(f[i])表示众数为(i)的贡献，那么
(f[i]=sum_{j<i}min(A[j],B[i-j]))
其中大写的(a,b)表示次数，但是这个东西很难做，
考虑把它变成正常的卷积的形式，那么就转换成判定，
判定(f[i])是否能够达到阈值，那么显然就变成了只有(0,1)的卷积，
但是这样会超时，考虑阈值仅限于不超过一个常数就可以了
代码
#include <cstdio>
#include <cctype>
#include <queue>
#define rr register
using namespace std;
const int mod=998244353,N=100011,inv3=332748118; priority_queue<pair<int,int> >q;
int a[N],b[N],A[N],B[N],ff[N<<2],n,TOT[2],lim,gg[N<<2],ans[N<<2],Ans,Gmi[31],Imi[31];
inline signed iut(){
rr int ans=0; rr char c=getchar();
while (!isdigit(c)) c=getchar();
while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();
return ans;
}
inline signed min(int a,int b){return a<b?a:b;}
inline signed mo1(int x,int y){return x+y>=mod?x+y-mod:x+y;}
inline signed mo2(int x,int y){return x<y?x-y+mod:x-y;}
inline signed ksm(int x,int y){
rr int ans=1;
for (;y;y>>=1,x=1ll*x*x%mod)
if (y&1) ans=1ll*ans*x%mod;
return ans;
}
namespace Theoretic{
int rev[N<<2],LAST,tt[N<<2];
inline void Pro(int n){
if (LAST==n) return; LAST=n;
for (rr int i=0;i<n;++i)
rev[i]=(rev[i>>1]>>1)|((i&1)?n>>1:0);
}
inline void NTT(int *f,int n,int op){
Pro(n);
for (rr int i=0;i<n;++i)
if (i<rev[i]) swap(f[i],f[rev[i]]);
rr int p=2,len=1;
for (rr int o=1;p<=n;++o){
rr int W=(op==1)?Gmi[o]:Imi[o];
for (rr int i=0;i<n;i+=p){
rr int t=1;
for (rr int j=i;j<i+len;++j){
rr int z=1ll*f[len+j]*t%mod;
f[len+j]=mo2(f[j],z),f[j]=mo1(f[j],z);
t=1ll*t*W%mod;
}
}
p<<=1,len<<=1;
}
}
inline void Cb(int *f,int *g,int n){
for (rr int i=0;i<n;++i) f[i]=1ll*f[i]*g[i]%mod;
}
inline void times(int *f,int *g,int len,int lim){
rr int n=1,invn; for (;n<lim;n<<=1);
for (rr int i=0;i<len;++i) tt[i]=g[i];
for (rr int i=len;i<n;++i) tt[i]=0;
NTT(f,n,1),NTT(tt,n,1),Cb(f,tt,n),NTT(f,n,-1);
for (rr int i=lim;i<n;++i) f[i]=0;
for (rr int i=0;i<n;++i) tt[i]=0;
invn=ksm(n,mod-2);
for (rr int i=0;i<lim;++i)
f[i]=1ll*f[i]*invn%mod;
}
}
inline void GmiImi(){
for (rr int i=0;i<31;++i) Gmi[i]=ksm(3,(mod-1)/(1<<i));
for (rr int i=0;i<31;++i) Imi[i]=ksm(inv3,(mod-1)/(1<<i));
}
inline void Prep(int lim){
for (rr int i=1;i<=n;++i) ff[i]=a[i]>=lim;
for (rr int i=1;i<=n;++i) gg[i]=b[i]>=lim;
Theoretic::times(ff,gg,n,n*2);
for (rr int i=1;i<=n;++i) ans[i]+=ff[i];
}
signed main(){
n=iut(),GmiImi();
for (rr int i=1;i<=n;++i) ++a[iut()];
for (rr int i=1;i<=n;++i) ++b[iut()];
for (rr int i=1;i<N;++i) if (a[i]) q.push(make_pair(a[i],0));
for (rr int i=1;i<N;++i) if (b[i]) q.push(make_pair(b[i],1));
while (!q.empty()){
rr int t=q.top().second; q.pop();
if ((++TOT[t])*TOT[t^1]>1e8) break;
}
if (!q.empty()) lim=q.top().first+1;
for (rr int i=1;i<=lim;++i) Prep(i);
for (rr int i=1;i<=n;++i) if (a[i]>lim) A[++A[0]]=i;
for (rr int i=1;i<=n;++i) if (b[i]>lim) B[++B[0]]=i;
for (rr int i=1;i<=A[0];++i)
for (rr int j=1;j<=B[0];++j)
ans[A[i]+B[j]]+=min(a[A[i]],b[B[j]])-lim;
for (rr int i=1;i<=2*n;++i)
if (Ans<ans[i]) Ans=ans[i];
return !printf("%d",Ans);
}