求助WaOn56
查看原帖
求助WaOn56
428358
Grisses楼主2025/2/3 20:50

rt,目前已确认不是模数问题。

#include<bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define mp(a,b) make_pair(a,b)
using namespace std;
const int mod=469762049,G=3;
int fpow(int a,int b){
	b=(b%(mod-1)+mod-1)%(mod-1);
	int res=1;
	while(b){
		if(b&1)res=res*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return res;
}
vector<int>rev;
void reverse(int len,vector<int>&f){
	rev.resize(len);
	rev[0]=0;
	for(int i=0;i<len;i++){
		rev[i]=rev[i>>1]>>1;
		if(i&1)rev[i]|=(len>>1);
		if(rev[i]>i)swap(f[i],f[rev[i]]);
	}
}
void NTT(vector<int>&f,int len,int op){
	reverse(len,f);
	for(int l=2;l<=len;l<<=1){
		int wn=fpow(G,op*(mod-1)/l);
		for(int j=0;j<len;j+=l){
			int w=1;
			for(int i=j;i<j+l/2;i++){
				int g=f[i],h=w*f[i+l/2]%mod;
				f[i]=(g+h)%mod;
				f[i+l/2]=(g-h+mod)%mod;
				w=w*wn%mod;
			}
		}
	}
	if(op==-1){
		int inv=fpow(len,mod-2);
		for(int i=0;i<len;i++)f[i]=f[i]*inv%mod;
	}
}
int n,m;
char s[2000005],t[2000005];
deque<int>a,b;
int val[30];
void Sol(vector<int>&A,deque<int>&S){
	if(A.empty())return;
	int l=A.size();
	reverse(A.begin(),A.end());
//	cerr<<"_+"<<l<<endl;
	while(S.size()>=l){
		vector<int>B,C=A;
		for(int i=0;i<min((int)S.size(),l+l-1);i++)B.push_back(S[i]);
		int ll=B.size(),len=1;
		while(len<l+ll)len<<=1;
		if(len>5e6)exit(1);
		vector<int>X(len),Y(len),Z(len);
		while(B.size()<len)B.push_back(0);
		while(C.size()<len)C.push_back(0);
		for(int i=0;i<len;i++)X[i]=B[i],Y[i]=C[i]*C[i]%mod*C[i]%mod;
		NTT(X,len,1);
		NTT(Y,len,1);
		for(int i=0;i<len;i++)Z[i]=(Z[i]+X[i]*Y[i]%mod)%mod;
		
		for(int i=0;i<len;i++)X[i]=B[i]*B[i]%mod,Y[i]=C[i]*C[i]%mod;
		NTT(X,len,1);
		NTT(Y,len,1);
		for(int i=0;i<len;i++)Z[i]=(Z[i]-2*X[i]%mod*Y[i]%mod+mod)%mod;
		
		for(int i=0;i<len;i++)X[i]=B[i]*B[i]%mod*B[i]%mod,Y[i]=C[i];
		NTT(X,len,1);
		NTT(Y,len,1);
		for(int i=0;i<len;i++)Z[i]=(Z[i]+X[i]*Y[i]%mod)%mod;
		
		NTT(Z,len,-1);
		for(int i=l-1;i<l+l-1;i++){
			if(Z[i]==0){
				for(int j=0;j<i+1;j++)S.pop_front();
				return;
			}
		}
		for(int i=0;i<l;i++)S.pop_front();
	}
	puts("No");
	exit(0);
}
mt19937_64 Rand(time(0));
signed main()
{
	for(int i=1;i<=26;i++)val[i]=Rand()%mod;
	scanf("%lld%lld%s%s",&n,&m,s+1,t+1);
	for(int i=1;i<=n;i++){
		if(s[i]=='-')a.push_back(0);
		else if(s[i]=='*')a.push_back(-1);
		else a.push_back(val[s[i]-'a'+1]);
	}
	for(int i=1;i<=m;i++){
		if(t[i]=='-')b.push_back(0);
		else if(t[i]=='*')b.push_back(-1);
		else b.push_back(val[t[i]-'a'+1]);
	}
	while(!a.empty()&&!b.empty()&&a.front()!=-1&&b.front()!=-1){
		int x=a.front(),y=b.front();
		a.pop_front();
		b.pop_front();
		if(x*y%mod*(x-y)%mod!=0){
			puts("No");
			return 0;
		}
	}
	while(!a.empty()&&!b.empty()&&a.back()!=-1&&b.back()!=-1){
		int x=a.back(),y=b.back();
		a.pop_back();
		b.pop_back();
		if(x*y%mod*(x-y)%mod!=0){
			puts("No");
			return 0;
		}
	}
	if(a.empty()||b.empty()){
		if(a.empty()&&b.empty())puts("Yes");
		else{
			if(a.empty())swap(a,b);
			bool f=1;
			for(int x:a)f&=(x==-1);
			if(f)puts("Yes");
			else puts("No");
		}
		return 0;
	}
	int s0=0,s1=0;
	for(int x:a)s0+=(x==-1);
	for(int x:b)s1+=(x==-1);
	if(s0&&s1){
		puts("Yes");
		return 0;
	}
	if(s1)swap(a,b);
	vector<int>las;
//	for(int x:a)cerr<<x<<' ';cerr<<endl;
//	for(int x:b)cerr<<x<<' ';cerr<<endl;
	for(int i=1;i<a.size();i++){
		if(a[i]==-1){
			Sol(las,b);
			las.clear();
//			for(int x:b)cerr<<x<<" ";
//			cerr<<endl;
		}
		else las.push_back(a[i]);
	}
	puts("Yes");
	return 0;
}
2025/2/3 20:50
加载中...