比赛 |
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;
}