提交记录 8954


用户 题目 状态 得分 用时 内存 语言 代码长度
wangtian1213 1002i. 【模板题】多项式乘法 Accepted 100 82.232 ms 158852 KB C++11 1.67 KB
提交时间 评测时间
2019-03-26 17:46:03 2020-08-01 01:27:37
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
const int N=5e6+5;

//复数类型 
const double Pi=acos(-1.0);    //π的值
struct complex {  //复数类型 
	double x,y;   //x为常数,y为sqrt(-1)的系数 
	complex (double xx=0,double yy=0) { x=xx,y=yy; }
} A[N],B[N];
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); }  //复数乘法  
int len,n,m,r[N],l; 

//FFT 点值表示法与系数表示法的互换 
void FFT(complex *A,int P) {  //A为系数,P的解释见下面
	for (int i=0; i<len; i++)
		if (i<r[i]) swap(A[i],A[r[i]]);  //求出迭代的序列
	for (int mid=1; mid<len; mid<<=1) {  //这次要合并的区间的长度的一半
		complex Wn(cos(Pi/mid),P*sin(Pi/mid));  //用欧拉定理求单位根		 
		for (int j=0; j<len; j+=(mid<<1)) { //(mid<<1)为区间长度,j为当前位置
			complex w(1,0);  //0次方幂
			for (int k=0; k<mid; k++,w=w*Wn) { //枚举左半部分的区间
				complex x=A[j+k],y=w*A[j+mid+k];  //用蝴蝶效应分奇偶算多项式
				A[j+k]=x+y; 
				A[j+mid+k]=x-y;     //左边的答案与右边的答案只有系数不同
			}
		}
	}
}		 

int main() {
	scanf("%d%d",&n,&m);
	for (int i=0; i<=n; i++) scanf("%lf",&A[i].x); //代表A中x^0,x^1,x^2……的系数 
	for (int i=0; i<=m; i++) scanf("%lf",&B[i].x); //和A意义相似
	len=1; while (len<=n+m) len<<=1,l++;          //len为单位w的最大幂次方
	for (int i=0; i<len; i++)
		r[i]=(r[i>>1]>>1)|((i&1)<<(l-1)); 
	//蝴蝶定理
	// 在原序列中 i 与 i/2 的关系是 : i可以看做是i/2的二进制上的每一位左移一位得来
    // 那么在反转后的数组中就需要右移一位,同时特殊处理一下奇数  
    
	FFT(A,1); FFT(B,1);     //1表示从系数->点值,-1表示从点值->系数   
	for (int i=0; i<=len; i++) A[i]=A[i]*B[i]; //向量乘法
	FFT(A,-1);    
	for (int i=0; i<=n+m; i++)   
		printf("%d ",(int)(A[i].x/len+0.5));   //四舍五入,这里除以len是因为公式(见附本)
	return 0;
}

CompilationN/AN/ACompile OKScore: N/A

Subtask #1 Testcase #117.096 ms152 MB + 648 KBAcceptedScore: 0

Subtask #1 Testcase #281.823 ms155 MB + 52 KBAcceptedScore: 100

Subtask #1 Testcase #347.545 ms153 MB + 416 KBAcceptedScore: 0

Subtask #1 Testcase #446.801 ms153 MB + 404 KBAcceptedScore: 0

Subtask #1 Testcase #518 ms152 MB + 648 KBAcceptedScore: 0

Subtask #1 Testcase #617.091 ms152 MB + 648 KBAcceptedScore: 0

Subtask #1 Testcase #718 ms152 MB + 648 KBAcceptedScore: 0

Subtask #1 Testcase #876.128 ms154 MB + 808 KBAcceptedScore: 0

Subtask #1 Testcase #975.792 ms154 MB + 808 KBAcceptedScore: 0

Subtask #1 Testcase #1069.686 ms154 MB + 540 KBAcceptedScore: 0

Subtask #1 Testcase #1182.019 ms155 MB + 132 KBAcceptedScore: 0

Subtask #1 Testcase #1282.232 ms154 MB + 12 KBAcceptedScore: 0

Subtask #1 Testcase #1317.136 ms152 MB + 648 KBAcceptedScore: 0


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