提交记录 16214


用户 题目 状态 得分 用时 内存 语言 代码长度
zhoufangyuanPT 1002. 测测你的多项式乘法 Compile Error 0 0 ns 0 KB C++ 1.41 KB
提交时间 评测时间
2021-05-07 21:40:12 2021-05-07 21:40:14
#include<cmath>
#include<cstdio>
#include<cstring>
using namespace std;
#define PI 3.14159265358979323846
struct complex
{
double real,image;
};
inline complex operator+(complex x,complex y){return (complex){x.real+y.real,x.image+y.image};}
inline complex operator-(complex x,complex y){return (complex){x.real-y.real,x.image-y.image};}
inline complex operator*(complex x,complex y){return (complex){x.real*y.real-x.image*y.image,x.real*y.image+x.image*y.real};}
struct node
{
complex a[2097152];
void fft(int);
}A,B;int len;
int r[2097152];
complex w[2097152];
void node::fft(int type)
{
for(int i=0;i<len;i++)if(i<r[i])a[i]^=a[r[i]]^=a[i]^=a[r[i]];
w[0]=(complex){1,0};
for(int i=1;i<len;i<<=1)
{
complex wi=(complex){cos(PI/i),type*sin(PI/i)};
for(int j=i-2;j>=2;j-=2)w[j]=w[j>>1];
for(int j=1;j<i;j+=2)w[j]=w[j-1]*wi;
for(int j=0;j<len;j+=i<<1)
{
for(int k=0;k<i;k++)
{
complex ak=a[j+k],awk=w[k]*a[i+j+k];
a[j+k]=ak+awk;a[i+j+k]=ak-awk;
}
}
}
}
void poly_multiply(unsigned *a,int n,unsigned *b,int m,unsigned *c)
{
len=1;int t=-1;
while(len<=n+m)len<<=1,t++;
r[0]=0;
for(int i=0;i<len;i++)r[i]=r[i>>1]>>1|(i&1)<<t;
for(int i=0;i<=n;i++)A.a[i]=(complex){a[i],0};
for(int i=n+1;i<len;i++)A.a[i]=(complex){0,0};
for(int i=0;i<=m;i++)B.a[i]=(complex){b[i],0};
for(int i=m+1;i<len;i++)B.a[i]=(complex){0,0};
A.fft(1);B.fft(1);
for(int i=0;i<len;i++)A.a[i]=A.a[i]*B.a[i];
A.fft(-1);
for(int i=0;i<=n+m;i++)c[i]=(unsigned)round(A.a[i].real/len);
}

CompilationN/AN/ACompile ErrorScore: N/A


Judge Duck Online | 评测鸭在线
Server Time: 2024-03-28 23:07:07 | Loaded in 1 ms | Server Status
个人娱乐项目,仅供学习交流使用