「bzoj4382」「POI2015」Podział naszyjnika - 字符串+Hash

题目大意

    长度为$n$的一串项链，每颗珠子是$k$种颜色之一。第$i$颗与第$i-1,i+1$颗珠子相邻，第$n$颗与第$1$颗也相邻。
    切两刀，把项链断成两条链。要求每种颜色的珠子只能出现在其中一条链中。
    求方案数量（保证至少存在一种），以及切成的两段长度之差绝对值的最小值。

---

题目分析

这篇文章讲得比较清楚。

补充一下。
以颜色作为分界线，对于每一种颜色，只能在同一个连通块内分割。
故对连通块作Hash，Hash相同的地方即可划分成两块。
若能得到Hash，剩下的就可以排序+双指针了。

普通的$O(nk)$的Hash不可行。
因为相邻两个位置颜色只差$1$，故可以放弃乘底数式Hash，直接采用相加的Hash，即可$O(1)$计算下一个的Hash值。
但这样Hash的准确度有所下降，使用双Hash即可解决。

注意对于每一种颜色，最后分界线后与第一个分界线前编号应该相同。

---

代码

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;

typedef long long LL;

inline const int Get_Int() {
	int num=0,bj=1;
	char x=getchar();
	while(x<'0'||x>'9') {
		if(x=='-')bj=-1;
		x=getchar();
	}
	while(x>='0'&&x<='9') {
		num=num*10+x-'0';
		x=getchar();
	}
	return num*bj;
}

const int maxn=1000005,mod=99995999;

LL n,k,v[maxn],a[maxn][2],b[maxn][2],Last[maxn],ans=0,ans2=mod;

struct Hash {
	int val[2],pos;
	bool operator < (const Hash& b) const {
		return val[0]<b.val[0]||(val[0]==b.val[0]&&val[1]<b.val[1]);
	}
	bool operator == (const Hash& b) const {
		return val[0]==b.val[0]&&val[1]==b.val[1];
	}
} Hash[maxn];

int main() {
	srand(99995999);
	n=Get_Int();
	k=Get_Int();
	for(int i=1; i<=n; i++)v[i]=Get_Int();
	for(int i=1; i<=k; i++) {
		a[i][0]=rand(); //底数
		a[i][1]=rand();
		b[i][0]=b[i][1]=1;
	}
	for(int i=n; i>=1; i--)if(!Last[v[i]])Last[v[i]]=i;
	Hash[0].val[0]=Hash[0].val[1]=k;
	for(int i=1; i<=n; i++)
		for(int id=0; id<=1; id++) {
			int x=v[i];
			Hash[i].val[id]=Hash[i-1].val[id]-b[x][id];
			b[x][id]=b[x][id]*a[x][id]%mod;
			if(Last[x]==i)b[x][id]=1;
			Hash[i].val[id]=(Hash[i].val[id]+b[x][id]+mod)%mod;
			Hash[i].pos=i;
		}
	sort(Hash+1,Hash+n+1);
	for(int i=1,j; i<=n; i=j) {
		j=i;
		int cnt=0;
		vector<LL> cur;
		while(Hash[j]==Hash[i]) {
			cnt++;
			cur.push_back(Hash[j].pos);
			j++;
		}
		ans+=(long long)(cnt-1)*cnt/2;
		sort(cur.begin(),cur.end());
		int k=1;
		for(auto x:cur) {
			while(k<cur.size()&&cur[k]-x<n/2)k++;
			if(k<cur.size())ans2=min(ans2,max(cur[k]-x,n-cur[k]+x)-min(cur[k]-x,n-cur[k]+x));
			ans2=min(ans2,max(cur[k-1]-x,n-cur[k-1]+x)-min(cur[k-1]-x,n-cur[k-1]+x));
			if(k==cur.size())break;
		}
	}
	printf("%lld %d\n",ans,ans2);
	return 0;
}