P6300

某种意义上让我想起了 P6371？

先考虑枚举拼出来的长度 $l$ 。设 $l$ 的答案为 $f_l$ ，长度为 $i$ 的木棍有 $c_i$ 个，则有

f_l=\left\lfloor\dfrac{1}{2}\sum_{i+j=l}\min(c_i,c_j)\right\rfloor

$\dfrac{1}{2}$ 的原因是若 $i\not=j$ ，则会被计算两次。否则要两个相同长度的木棍才能拼出来。

考虑怎么优化。看这个柿子发现就很像一个卷积的形式，但是 $\min$ 这种东西不好卷，考虑枚举 $\min(c_i,c_j)=k$ 提出来：

f_l=\left\lfloor\dfrac{1}{2}\sum_{i+j=l}\sum_{k\le n}([c_i\ge k]\times[c_j\ge k])\right\rfloor

可以放前面，先枚举 $k$ 然后每次卷一遍。

这样做的复杂度是 $O(n^2\log n)$ 的，还不如暴力。。。

那我们可以再拼一个暴力上去啊。

上面解法的瓶颈在于枚举 $k$ ，但是发现 $c_i$ 大的 $i$ 不会很多。考虑类似根号分治的东西，设置一个阈值 $B$ ，对于 $c_i\le B$ 的部分直接用上述做法。 $O(Bn\log n)$ 。否则发现只有 $min(c_i,c_j)> B$ 的 $(i,j)$ 才会产生额外贡献。这样的对只有 $O((\dfrac{n}{B})^2)$ 个，每个找出来暴力算即可。

考虑 $B$ 的设置。多项式常数相当大，那就在暴力部分能过的条件下尽可能调小 $B$ 。 $B=10$ 可过。

code：

int n,m,c[N],a[N],ans[N],to[N];
//模板
const int B=10;
void Yorushika(){
	scanf("%d%d",&n,&m);
	rep(i,1,n){
		int x;scanf("%d",&x);
		c[x]++;
	}
	vector<int> g;
	rep(j,1,m)if(c[j]>B)g.eb(j);
	for(int i:g)for(int j:g)ans[i+j]+=min(c[j],c[i])-B;
	int len=1;while(len<=m*2+1)len<<=1;
	rep(k,1,B){
		rep(i,0,len-1)a[i]=c[i]>=k;
		NTT(a,len,1);
		rep(i,0,len-1)a[i]=1ll*a[i]*a[i]%mod;
		NTT(a,len,0);
		rep(i,0,m*2)ans[i]+=a[i];
	}
	int a=0,b=0;
	rep(i,1,m*2)if(ans[i]/2>b)a=i,b=ans[i]/2;
	printf("%d %d\n",b,a);
}
signed main(){
	int t=1;
	//	scanf("%d",&t);
	while(t--)
		Yorushika();
}

感谢您的支持，我会继续努力的!