自动搬运

查看原文

来自洛谷，原作者为

	beng **

搬运于2025-08-24 21:49:33，当前版本为作者最后更新于2018-08-16 16:29:17，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

题目大意：

给出$n$个数，可将它们分为若干个串，每个串有$k$个数（长度不足$k$则丢弃），求使得不同的串最多的$k$值及串的个数。串可翻转，即子串$1,2,3$和$3,2,1$被认为是一样的。

思路：

本题朴素的思路是枚举$k$和各个串，比较各个串并记录不同的串，但这样比较和记录的时间复杂度不能做到$O(1)$，就肯定会超时。但如果比较和记录的时间复杂度是$O(1)$是不是就不会超时了呢？我们计算一下：

枚举$k$要$O(n)$的时间复杂度，而串有$\lfloor\dfrac{n}{k}\rfloor$个，所以枚举的时间复杂度为

$$\displaystyle\sum_{k=1}^n\lfloor\dfrac{n}{k}\rfloor $$

展开后得到

$$\lfloor\dfrac{n}{1}\rfloor+\lfloor\dfrac{n}{2}\rfloor+...+\lfloor\dfrac{n}{n}\rfloor $$

近似于

$$\dfrac{n}{1}+\dfrac{n}{2}+...+\dfrac{n}{n}$$

把$n$提出来得到

$$n(1+\dfrac{1}{2}+...+\dfrac{1}{n})$$

我们可以发现$1+\dfrac{1}{2}+...+\dfrac{1}{n}$为调和级数，有

$$1+\dfrac{1}{2}+...+\dfrac{1}{n}\approx\ln n<\log_2n $$

又因为我们的比较和记录的时间复杂度是$O(1)$的，所以总共的时间复杂度便是$O(n\log n)$。

所以我们便可以想到使用哈希。

与一般的哈希一样，我们先从头弄一个前缀哈希和幂数组，这样若要求$i$到$j$位数字的哈希值便可以用$hash[j]-hash[i-1]*power[j-i+1]$这样来进行计算。但特别的，这题规定串是可以翻转的，所以我们也要从尾弄一个后缀哈希，与前面一样，只不过顺序相反罢了。要求$i$到$j$位数字的哈希值可以这样计算：$hash[i]-hash[j+1]*power[j-i+1]$。这样，查询某个子串便可以这样实现$O(1)$查询。为了不冲突，此处$power$每次要乘一个很大的质数才行，这里需要注意。

那么我们的哈希怎么判重呢？我们可以用除余法，若冲突则在下一位保存。如果我们在判重时正反顺序两个都不冲突，我们才认为它是新串，并将正反顺序的哈希值保存下来。

但是我们这里每枚举一次$k$，都要清空判重数组，这样的时间复杂度是很高的，怎么办呢？我们可以用一个$time$数组，表示使用当前位的时间，若他的值为规定的时间，就说明它在当前时间被更新过了，就要对当前位的数进行判重，否则说明这个值只是在之前的时间被更新过，与现在无关，就表明当前位无值。这样就不用每次都更新判重数组了。

其他记录答案什么的就是朴素的暴力做法啦~

代码：

#include<cstdio>//以下为了防止不必要的错误，类型我全都开成了unsigned long long
unsigned long long n,m,i,j1,j2,k,max,nans,ans[200005],a[200005],hash[1000007],b[1000007],power[200005],ha1[200005],ha2[200005];//此处的hash为判重数组，b为time数组，power为幂数组，ha1为前缀哈希，ha2为后缀哈希
unsigned long long ha(unsigned long long x)//判重
{
	unsigned long long y=x%1000007;
	if (b[y]==m&&hash[y]!=x)
	{
		y++;
		if (y==n/m)
		y=0;
	}
	return y;
}
int main()
{
	scanf("%d",&n);
	power[0]=1;
	for (m=1;m<=n;m++)
	scanf("%d",&a[m]),power[m]=power[m-1]*19260817,ha1[m]=ha1[m-1]*19260817+a[m];//读入并预处理幂数组与前缀哈希
	for (m=n;m;m--)
	ha2[m]=ha2[m+1]*19260817+a[m];//预处理后缀哈希
	for (m=1;m<=n;m++)//枚举题目中的k
	{
		k=0;//k为不同串的个数
		for (i=m+1;i<=n+1;i+=m)
		{
			j1=ha(ha1[i-1]-ha1[i-m-1]*power[m]);
			if (hash[j1]==ha1[i-1]-ha1[i-m-1]*power[m])//判断正序是否重复
			continue;
			j2=ha(ha2[i-m]-ha2[i]*power[m]);
			if (hash[j2]==ha2[i-m]-ha2[i]*power[m])//判断反序是否重复
			continue;
			b[j1]=b[j2]=m,hash[j1]=ha1[i-1]-ha1[i-m-1]*power[m],hash[j2]=ha2[i-m]-ha2[i]*power[m],k++;//记录时间戳，保存正反顺序两个串
		}
		//以下为记录答案
		if (k>max)
		max=k,nans=1,ans[1]=m;
		else
		if (k==max)
		nans++,ans[nans]=m;
	}
	printf("%lld %lld\n",max,nans);
	for (m=1;m<=nans;m++)
	printf("%lld ",ans[m]);
	return 0;
}