专栏文章

题解：P6300 悔改

wwwt100127
P6300题解参与者 3已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@mipt7zti
此快照首次捕获于
2025/12/03 17:33
3 个月前
此快照最后确认于
2025/12/03 17:33
3 个月前
查看原文

题目描述

给定一些长度的木棍，两两组合，求可组成的长度组成数量的最大值和此时组成的长度。

思路

First

设 ckc_k 表示长度为 kk 的有多少个，anskans_k 表示答案是 kk 时，数量的最大值。
显然答案即求 anskans_k 的最大值。
容易想到 anskans_k 的表示如下：
ansk=12∑i+j=kmin⁡(ci,cj)ans_k = \frac{1}{2} \sum_{i+j=k} \min(c_i,c_j)
（其中的 12\frac{1}{2} 需要注意）
设 KK 表示一共有多少个 ci≠0c_i \ne 0，则时间复杂度为 O(K2)O(K^2)。
这种方法适用于 KK 较小的时候（或者说，所有的 cic_i 都比较大的时候）。

Second

我们接着往下想。
发现 i+j=ki+j=k 十分像卷积。
（废话，标签都告诉你了）
但是是对 min⁡(ci,cj)\min(c_i,c_j) 求和，考虑枚举 min⁡(ci,cj)\min(c_i,c_j)。
ansk=12∑i+j=kmin⁡(ci,cj)=12∑d=1n∑i+j=k[ci≥d][cj≥d]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]
然后发现：复杂度似乎变高了？
我知道你很急，但你先别急。
设 KK 表示一共有多少个 ci≠0c_i \ne 0，则时间复杂度是 O(Kmlog⁡m)O(Km \log m)。

Third

如果将以上两种合并呢（类似根号分治）？
不妨：当 i≥si \ge s 时用法一，i≤s−1i \le s-1 时用法二。
则时间复杂度变成 O(smlog⁡m+n2s2)O(sm \log m + \frac{n^2}{s^2})。
当 smlog⁡m=n2s2s m \log m = \frac{n^2}{s^2}，即 s=n2mlog⁡m3s= \sqrt[3]{ \frac{n^2}{m \log m} } 时时间复杂度最优。
不妨设 nn，mm 在同一数量级，则 s=nlog⁡n3s= \sqrt[3]{\frac{n}{ \log n}}，时间复杂度为 O((n4log⁡2n)13)O((n^4 \log^2 n )^ \frac{1}{3} )。

Last

两部分有重复计算，减去即可。
代码如下：
CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
int read(){int x=0; bool flag=1; char ch=getchar();
	while(ch<'0' || ch>'9'){if(ch=='-') flag=0;ch=getchar();}
	while(ch>='0' && ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
	return flag? x:-x;}
void write(int x,char ch=0){if(x<0) x=-x,putchar('-');
	static short s[35],top=-1;do{s[++top]=x%10;x/=10;}while(x);
	while(~top) putchar(s[top--]+48);if(ch) putchar(ch);}
int ksm(int a,int b,int p)
{
	int ans=1%p;
	while(b)
	{
		if(b&1)
		ans=ans*a%p;
		a=a*a%p;
		b>>=1;
	}
	return ans;
}
const int N=1e6+5;
const int Max_Num=13;
const int mod=998244353;
const int INF=0x3f3f3f3f3f3f3f3fll;
const int Base=3;
const int rBase=332748118;
int n,m;
int a[N];
int ans[N];

namespace NTT
{
	int A[N],rev[N];
	int limit,Li;
	void init()
	{
		limit=1,Li=0;
		while(limit<=m*2) limit<<=1,Li++;
		for(int i=0;i<limit;i++) rev[i]=((rev[i>>1]>>1)|((i&1)<<(Li-1)));
	}
	void Clear(int A[],int n){for(int i=0;i<n;i++) A[i]=0;}
	void solve(int F[],int t)
	{
		int i,j,mid;
		for(i=0;i<limit;i++)
		{
			if(i<rev[i])
			swap(F[i],F[rev[i]]);
		}
		
		for(mid=1;mid<limit;mid<<=1)
		{
			int step=ksm(t==1? Base:rBase,(mod-1)/(mid<<1),mod);
			for(i=0;i<limit;i+=(mid<<1))
			{
				int cur=1;
				for(j=0;j<mid;j++,cur=cur*step%mod)
				{
					int x=F[i+j],y=cur*F[i+j+mid]%mod;
					F[i+j]=(x+y)%mod;
					F[i+j+mid]=(x-y+mod)%mod;
				}
			}
		}
		
		if(t==-1)
		{
			int inv=ksm(limit,mod-2,mod);
			for(i=0;i<limit;i++)
			F[i]=F[i]*inv%mod;
		}
	}
	void Just_Do_It(int k)
	{
		int i;
		Clear(A,limit);
		for(i=1;i<=m;i++) A[i]=(a[i]>=k);
		solve(A,1);
		for(i=0;i<limit;i++) A[i]=A[i]*A[i];
		solve(A,-1);
		for(i=0;i<limit;i++) ans[i]+=A[i];
	}
}

vector<int> Wzn;
signed main()
{
	int i;
	n=read(),m=read();
	for(i=1;i<=n;i++) a[read()]++;
	NTT::init();
	for(i=1;i<=Max_Num;i++) NTT::Just_Do_It(i);
	
	for(i=1;i<=m;i++)
	{
		if(a[i]>Max_Num)
		Wzn.push_back(i);
	}
	for(auto i:Wzn)
	{
		for(auto j:Wzn)
		ans[i+j]+=min(a[i],a[j])-Max_Num;
	}
	for(i=1;i<NTT::limit;i++) ans[i]/=2;
	
	int Ans[2]={0,INF};
	for(i=1;i<NTT::limit;i++)
	{
		if(Ans[0]<ans[i] || (Ans[0]==ans[i] && Ans[1]>i))
		Ans[0]=ans[i],Ans[1]=i;
	}
	write(Ans[0],' '),write(Ans[1],'\n');
	return 0;
}

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...