比赛 hs的新题赛 评测结果 AAAAAAAAAA
题目名称 异或前缀和 最终得分 100
用户昵称 梦那边的美好ET 运行时间 1.750 s
代码语言 C++ 内存使用 42.07 MiB
提交时间 2019-04-04 11:35:04
显示代码纯文本
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#define LL long long 
#define maxn 1200010
using namespace std;
const LL mod=998244353,g=3;
LL ksm(LL x,LL y){
	LL ans=1;
	while(y){
		if(y&1)ans=(ans*x)%mod;
		x=(x*x)%mod;y>>=1;
	}
	return ans;
}
char s1[maxn],s2[maxn];
LL a1[maxn],a2[maxn],a3[maxn],n=1,f[maxn];
void NTT(LL *A,LL DFT){
	for(int i=0;i<n;i++)if(i<f[i])swap(A[i],A[f[i]]);
	for(int s=1;s<n;s<<=1){
		LL wn=ksm(g,(mod-1)/(s<<1));
		if(DFT==-1)wn=ksm(wn,mod-2);
		for(int i=0;i<n;i+=(s<<1)){
			LL w1=(LL)1;
			for(int j=i;j<i+s;j++){
				LL x=A[j],y=(A[j+s]*w1)%mod;
				A[j]=(x+y)%mod;A[j+s]=(x-y+mod)%mod;
				w1=(w1*wn)%mod;
			}
		}
	}
	if(DFT==-1){LL fz=ksm(n,mod-2);for(int i=0;i<n;i++)A[i]=(A[i]*fz)%mod;}
	return;
}
int main(){
	freopen("hshshs.in","r",stdin);
	freopen("hshshs.out","w",stdout);
	LL l1,l2;
	scanf("%s%s",s1,s2);l1=strlen(s1);l2=strlen(s2);l1--,l2--;
	while(n<=l1+l2)n<<=1;
	for(int i=1;i<n;i++)f[i]=(f[i>>1]>>1)|((i&1)?n>>1:0);
	for(int i=0;i<=l1;i++)a1[i]=s1[l1-i]-'0';
	for(int i=0;i<=l2;i++)a2[i]=s2[l2-i]-'0';
	NTT(a1,1);NTT(a2,1);
	for(int i=0;i<n;i++)a3[i]=(a1[i]*a2[i])%mod;
	NTT(a3,-1);
	for(int i=0;i<n;i++)a3[i+1]+=a3[i]/10,a3[i]%=10;
	while(a3[n]==0&&n!=0)n--;
	LL hs=0;
	for(int i=n;i>=0;i--)hs=(hs*10+a3[i])%4;
	if(hs==0){for(int i=n;i>=0;i--)printf("%d",a3[i]);printf("\n");}
	if(hs==1)printf("1\n");
	if(hs==2){
	    a3[0]++;LL p=0;while(a3[p]>=10)a3[p]=0,a3[p+1]++,p++;n=max(n,p);
	    for(int i=n;i>=0;i--)printf("%d",a3[i]);printf("\n");
	}
	if(hs==3)printf("0\n");
	return 0;
}