听灌多,帮卡常 悬棺
  • 板块灌水区
  • 楼主LinkCatTree
  • 当前回复3
  • 已保存回复3
  • 发布时间2024/8/29 19:41
  • 上次更新2024/8/29 22:37:01
查看原帖
听灌多,帮卡常 悬棺
806330
LinkCatTree楼主2024/8/29 19:41
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll J=1e18,mod=1e9+9,B[2]={211,213};
const ll N=1e5+7;
inline ll qp(ll x,ll y=mod-2LL) {return y?(y&1?x:1)*qp(x*x%mod,y>>1)%mod:1LL;}
ll pw[N][2],pv[N][2],ans;
ll af[N][2],ab[N][2],bf[N][2],bb[N][2];
ll n,m; ll a[N],b[N];

inline bool chk(ll len,ll c) {
	unordered_map<ll,ll> mp;
	for(ll i=1;i+(len<<1)+c<=n+1;i++) {
		ll ha[2],hb[2];
		for(ll j=0;j<2;j++)
			ha[j]=(af[i+len-1][j]+mod-af[i-1][j]*pw[len][j]%mod)%mod,
			hb[j]=(ab[i+len+c][j]+mod-ab[i+len*2+c][j]*pw[len][j]%mod)%mod;
		mp[(ha[0]+mod-hb[0])%mod*mod+(ha[1]+mod-hb[1])%mod]=1;
	}
	for(ll i=1;i+(len<<1)+c<=m+1;i++) {
		ll ha[2],hb[2];
		for(ll j=0;j<2;j++) {
			ha[j]=(bf[i+len-1][j]-bf[i-1][j]*pw[len][j]%mod+mod)%mod;
			hb[j]=(bb[i+len+c][j]-bb[i+len*2+c][j]*pw[len][j]%mod+mod)%mod;
		}
		if(mp[(hb[0]+mod-ha[0])%mod*mod+(hb[1]+mod-ha[1])%mod]) return true;
	}
	return false;
}

inline ll getll() {
	ll res=0; int ch=getchar();
	while(ch<'0'||ch>'9') ch=getchar();
	for(;ch>='0'&&ch<='9';ch=getchar())
		res=(res<<3)+(res<<1)+(ch^48);
	return res;
}

int main() {
	for(ll j=0;j<2;j++) {
		pw[0][j]=1;
		for(ll i=1;i<N;i++) pw[i][j]=pw[i-1][j]*B[j]%mod;
		for(ll i=0;i<N;i++) pv[i][j]=qp(pw[i][j]);
	}
	n=getll(),m=getll();
	for(ll i=1;i<=n;i++) a[i]=(ll)getll();
	for(ll i=1;i<=m;i++) b[i]=(ll)getll();
	for(ll j=0;j<2;j++) {
		for(ll i=1;i<=n;i++) af[i][j]=(af[i-1][j]*B[j]+a[i])%mod;
		for(ll i=n;i;i--) ab[i][j]=(ab[i+1][j]*B[j]+a[i])%mod;
		for(ll i=1;i<=m;i++) bf[i][j]=(bf[i-1][j]*B[j]+b[i])%mod;
		for(ll i=m;i;i--) bb[i][j]=(bb[i+1][j]*B[j]+b[i])%mod;
	}
	for(ll c=0;c<2;c++) {
		ll l=0,r=min(n,m)/2;
		ll res=0,mid;
		while(l<=r) {
			mid=l+r>>1;
			if(chk(mid,c)) res=mid,l=mid+1;
			else r=mid-1;
		}
		ans=max(ans,res*2+c);
	}
	printf("%lld\n",ans);
	return 0;
}
2024/8/29 19:41
加载中...