sequence(2018.10.23)

建出差分序列，可以发现最早出现的回文串就是答案，自己想想就懂了。

\(O(N)\)找出回文串就好了，字符串\(hash\)或者\(manacher\)都能在合法时间内得到答案。

#include<cstdio>

#include<algorithm>

using namespace std;

const int mod=1e9+7;

int flag,n,d[2000001],pos[2000001],h[20000001],q[20000002],k=233;

int main()

{

	scanf("%d",&n);

	for(int i=1;i<=n;i++)scanf("%d",&d[i]),d[i+n]=d[i];

	for(int i=1;i<2*n;i++)d[i]=d[i+1]-d[i]+1000000;

	pos[0]=1;if(n<3){printf("0\n");return 0;}

	for(int i=1;i<2*n;i++)pos[i]=(1ll*pos[i-1]*k)%mod;

	for(int i=1;i<2*n;i++)h[i]=(1ll*h[i-1]*k+d[i])%mod;

	for(int i=2*n-1;i>=1;i--)q[i]=(1ll*q[i+1]*k+d[i])%mod;

	for(int i=n-1;i<2*n;i++)

	{

		int a=(h[i]-1ll*h[i-n+1]*pos[n-1]%mod+mod)%mod,b=(q[i-n+2]-1ll*q[i+1]*pos[n-1]%mod+mod)%mod;

		if(a==b){printf("%d\n",i-n+1);return 0;}

	}

	printf("IMPOSSIBLE\n");

}

巴特西

sequence(2018.10.23)

最新文章

热门文章