19-10-18-Y

ZJ一下：

感觉能拿到的分都拿到了，至于后来改题就缶了

其实是：太tui导致没改好

TJ：

T1：

正解是$mathsf{KMP}$，但是广大群众都用了$mathsf{hash}$……

发现了一个巨的素数，它太好看辣！

$$underbrace{1111111111111111111}_{19个1}$$

#include <iostream>
#include <cstring>
#include <cstdio>
#define L 1111111
#define LL long long

using namespace std;

const int Mod=1e9+9,Upbit=4373;//1111111111111111111
int tim,len;
char st[L];
LL hsp[L],hsp2[L];
LL pubh,sths;
LL lva,rva;
LL ans=0;

LL ppow(LL a,LL b){
	LL res=1;
	a%=Mod;
	b%=Mod-1;
	while(b){
		if(b&1)res=res*a%Mod;
		a=a*a%Mod;
		b>>=1;
	}
	return res;
}
inline LL tur(const char ch){
	return ch-'A'+1;
}
int main(){
//	freopen("ccx.in" ,"r",stdin);
//	freopen("ccx.out","w",stdout);
	hsp[0]=1;
	for(int i=1;i<=1000000;i++)
		hsp[i]=hsp[i-1]*Upbit%Mod;
	int T;
	cin>>T;
	while(T--){
		memset(hsp2,0,sizeof hsp2);
		ans=sths=pubh=0;
		scanf("%d%d%s",&tim,&len,st+1);
//		puts("Inputend");
		for(int i=1;i<=len;i++)
			sths=(sths*Upbit%Mod+tur(st[i]))%Mod;
//		puts("String hash end");
		hsp2[0]=ppow(Upbit,1ll*len*(tim-1));
		for(int i=1;i<=len;i++)
			hsp2[i]=hsp2[i-1]*Upbit%Mod;
//		puts("Hash tim*len end");
		for(int i=1;i<tim;i++)
			pubh=(pubh*hsp[len]%Mod+sths)%Mod;
//		puts("One Hash end");
		rva=lva=pubh;
		ans=1ll*len*(tim-1);
//		puts("Start Che!");
		for(int r=1,l=len;r<len;r++,l--){
			rva=(rva*Upbit%Mod+tur(st[r]))%Mod;//Add
			lva=(lva+hsp2[r-1]*tur(st[l])%Mod)%Mod;
//			cout<<r<<" "<<l<<" "<<rva<<" "<<lva<<endl;
			if(rva==lva)
				ans=max(ans,1ll*r+1ll*len*(tim-1));
//			cout<<ans<<endl;
		}
//		puts("end Che!");
		if(ans==0)ans=-1;
		printf("%lld
",ans);
	}
}

T2

因为tui改T3而没看

T3

可以使用倍增或是树剖完成。

但是现在方法也没有人成功用树剖AC。

有人成功了嘛，可以在下面评论。

（咕！）