MnZn 求助卡常
查看原帖
MnZn 求助卡常
310818
蒟酱厂妹楼主2022/7/25 08:16
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define siz(x) (int)(x).size()
using std::cin;using std::cout;
constexpr int kN=2e7+1;
std::string a,b;
long long ans1,ans2;
signed main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	std::ios::sync_with_stdio(false);cin.tie(nullptr);
	a.reserve(kN),b.reserve(kN+1);
	cin>>a>>b;
	std::basic_string<int>z(siz(b),0);
	z[0]=siz(b);
	for(int i=1,l=-1,r=-1;i<siz(b);i++){
		if(i<=r)z[i]=std::min(z[i-l],r-i+1);
		while(z[i]+i<siz(b)&&b[z[i]+i]==b[z[i]])z[i]++;
		if(z[i]+i-1>r)l=i,r=i+z[i]-1;
	}
	std::basic_string<int>p(siz(a),0);
	for(int i=0,l=-1,r=-1;i<siz(a);i++){
		if(i<=r)p[i]=std::min(z[i-l],r-i+1);
		while(p[i]+i<siz(a)&&a[p[i]+i]==b[p[i]])p[i]++;
		if(p[i]+i-1>r)l=i,r=i+p[i]-1;
	}
	for(int i=0;i<siz(z);i++)ans1^=1ll*(i+1)*(z[i]+1);
	for(int i=0;i<siz(p);i++)ans2^=1ll*(i+1)*(p[i]+1);
	cout<<ans1<<'\n'<<ans2;
	return 0;
}

rt,不开 O2 只能过前两个点(不是,为什么不把时限开大啊或者加上 O2 标签)

2022/7/25 08:16
加载中...