社区讨论

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 条回复,欢迎继续交流。

正在加载回复...