提交记录 22459


用户 题目 状态 得分 用时 内存 语言 代码长度
qwqwqwq 1004a. 【模板题】高精度乘法2 Accepted 100 3.427 ms 660 KB C++17 967 B
提交时间 评测时间
2024-09-01 14:26:08 2024-09-01 14:26:09
#pragma GCC optimize("Ofast")
#include<iostream>
#include<cstring>
using U=unsigned;using V=unsigned long long;constexpr U P=998244353,N=1<<15;constexpr U F(U a,U b){U c=1;for(;b;b/=2)b&1&&(c=(V)c*a%P),a=(V)a*a%P;return c;}U R[N],T[N]{0,1};void f(U*a){for(U b=1;b^N;b++)if(R[b]<b)a[b]^=a[R[b]]^=a[b]^=a[R[b]];for(U b=1,c,d,e,f;b^N;b*=2)for(c=0;c^N;c+=b*2)for(d=0;d^b;d++)e=a[c+d],f=(V)a[b+c+d]*T[b+d]%P,(a[c+d]=e+f)>=P&&(a[c+d]-=P),(a[b+c+d]=e-f)>=P&&(a[b+c+d]+=P);}main(){for(U a=1;a^N;a++)R[a]=(R[a/2]+a%2*N)/2;for(U a=2,b,c;a^N;a*=2)for(b=F(3,P/a/2),c=a/2;c^a;c++)T[c*2]=T[c],T[c*2+1]=(V)T[c]*b%P;std::cin.tie(0)->sync_with_stdio(0);U a,b,c[N]{},d[N]{};char x[N],y[N];std::cin>>x>>y,a=strlen(x)-1,b=strlen(y)-1;for(U e=0;e<=a;e++)c[e]=x[a-e]^48;for(U e=0;e<=b;e++)d[e]=y[b-e]^48;f(c),f(d);for(U e=0;e^N;e++)c[e]=(V)c[e]*d[e]%P;f(c);a+=b+1;for(U e=*d=0,f=F(N,P-2);e^a;e++)d[e]+=(V)c[(N-e)%N]*f%P,d[e+1]=d[e]/10,d[e]%=10;while(!d[a])a--;for(;~a;a--)std::cout<<d[a];}

CompilationN/AN/ACompile OKScore: N/A

Testcase #13.427 ms660 KBAcceptedScore: 100


Judge Duck Online | 评测鸭在线
Server Time: 2024-10-05 11:04:04 | Loaded in 0 ms | Server Status
个人娱乐项目,仅供学习交流使用