社区讨论
dalao帮忙改一下,改好了猴子(zzj)女装
P1919【模板】高精度乘法 / A*B Problem 升级版参与者 5已保存回复 6
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 6 条
- 当前快照
- 1 份
- 快照标识符
- @mi7rqx29
- 此快照首次捕获于
- 2025/11/21 02:32 4 个月前
- 此快照最后确认于
- 2025/11/21 02:32 4 个月前
帮忙改一下,改好了猴子(zzj)女装
CPP#include<cmath>
#include<cstdio>
using namespace std;
#define Max 60100
const double Pi=acos(-1);
inline double abss(double s){return s<0.0?-s:s;}
struct complex
{
double x,y;
complex(double xx=0,double yy=0)
{
x=xx;y=yy;
}
}b[Max<<2],c[Max<<2];int r[Max<<2];
char s[Max];
int ans[Max<<1];
complex operator + (complex a,complex b)
{
return complex(a.x+b.x,a.y+b.y);
}
complex operator - (complex a,complex b)
{
return complex(a.x-b.x,a.y-b.y);
}
complex operator * (complex a,complex b)
{
return complex(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);
}
complex operator / (complex a,complex b)
{
double tt=b.x*b.x+b.y*b.y;
return complex((a.x*b.x+a.y*b.y)/tt,(a.x*b.y-a.y*b.x)/tt);
}
int n,m;
inline void FFT(complex f[],short op)
{
for(int i=0;i<n;i++)if(i<r[i])
{
complex buf=f[i];
f[i]=f[r[i]];
f[r[i]]=buf;
}
for(int p=2;p<=n;p<<=1)
{
int len=p/2;
complex tmp(cos(Pi/len),sin(Pi/len)*op);
for(int k=0;k<n;k+=p)
{
complex buf(1,0);
for(int l=k;l<k+len;l++)
{
complex tt=f[l+len]*buf;
f[len+l]=f[l]-tt;
f[l]=f[l]+tt;
buf=buf*tmp;
}
}
}
}
int main()
{
scanf("%d",&n);n--;m=n;
scanf("%s",s);
for(int i=n;i>=0;i--)b[i].x=s[i]-'0';
scanf("%s",s);
for(int i=m;i>=0;i--)c[i].x=s[i]-'0';
for(m+=n,n=1;n<=m;n<<=1);
for(int i=0;i<n;i++)r[i]=(r[i>>1]>>1)|((i&1)?n>>1:0);
FFT(b,1);
FFT(c,1);
for(int i=0;i<n;i++)b[i]=b[i]*c[i];
FFT(b,-1);
for(int i=0;i<=m;i++)
{
ans[i]+=abss((b[i].x)/n);
if(ans[i]>10)
{
ans[i+1]+=ans[i]/10;
ans[i]%=10;
if(i==m)m++;
}
}
while(m>=0)printf("%d",ans[m--]);
return 0;
}
谢谢!
回复
共 6 条回复,欢迎继续交流。
正在加载回复...