提交记录 8049


用户 题目 状态 得分 用时 内存 语言 代码长度
wgr45097 1002i. 【模板题】多项式乘法 Accepted 100 91.523 ms 19132 KB C++ 2.04 KB
提交时间 评测时间
2019-01-27 22:44:16 2020-08-01 01:11:58
/*quick reference

const double PI = acos(-1);
std::complex<double> x = std::complex<double>(cos(2 * PI / n * i), sin(2 * PI / n * i))
std::complex<double> x_inv = std::conj(x);
double y = 1.414, q;
x.real(y);
q = floor( x.real() + 0.5 );

*/



#include<cstdio>
#include<cmath>
#include<complex>
#include<algorithm>
const int maxn = 5e5 + 5;
const double PI = acos(-1.0);
struct FastFourierTransform
{
	std::complex<double> A[maxn], omega[maxn], omegaInverse[maxn];
	int Rev(int x, int n)
	{
		n--;
		int ret = 0;
		while(n)
		{
			ret<<=1;
			if(x & 1)
				ret|=1;
			x>>=1, n>>=1;
		}
		return ret;
	}
	void init(int n)
	{
		for(int i = 0; i < n; i++)
		{
			omega[i] = std::complex<double>(cos(2 * PI / n * i), sin(2 * PI / n * i));
			omegaInverse[i] = std::conj(omega[i]);
		}
	}
	void transform(std::complex<double>* a, int n, std::complex<double>* omega)//in-place, n being power of 2
	{
		for(int i = 0; i < n; i++)
		{
			int rev = Rev(i, n);
			if(i < rev)
				std::swap(a[i], a[rev]);
		}
		for(int l = 2; l <= n; l <<= 1)//l/2 + l/2 -> l
			for(std::complex<double>* p = a; p != a + n; p += l)
			{
				int m = l >> 1;
				for(int i = 0; i < m; i++)
				{
					std::complex<double> t = omega[n / l * i] * p[i + m];
					p[i + m] = p[i] - t;
					p[i] += t;
				}
			}
	}
	void dft(std::complex<double>* a, int n)
	{
		transform(a, n, omega);
	}
	void idft(std::complex<double>* a,int n)
	{
		transform(a, n, omegaInverse);
		for(int i = 0; i < n; i++)
			a[i] /= n;
	}

}fft;

int c1[maxn], c2[maxn];
std::complex<double> a1[maxn], a2[maxn];

int main()
{
	int n, m, N = 1;
	scanf("%d%d", &n, &m);
	for(int i = 0; i <= n; i++)
		scanf("%d", c1 + i);
	for(int i = 0; i <= m; i++)
		scanf("%d", c2 + i);
	for(int i = 0; i <= n; i++)
		a1[i].real(c1[i]);
	for(int i = 0; i <= m; i++)
		a2[i].real(c2[i]);
	while(N < n + m + 1) N <<= 1;
	fft.init(N);
	fft.dft(a1, N);
	fft.dft(a2, N);
	for(int i = 0; i < N; i++)
		a1[i] *= a2[i];
	fft.idft(a1, N);
	for(int i = 0; i <= n + m; i++)
		c1[i] = floor( a1[i].real() + 0.5 );
	for(int i = 0; i <= n + m; i++)
		printf("%d ", c1[i]);
}

CompilationN/AN/ACompile OKScore: N/A

Subtask #1 Testcase #111.59 us40 KBAcceptedScore: 0

Subtask #1 Testcase #289.127 ms18 MB + 620 KBAcceptedScore: 0

Subtask #1 Testcase #338.618 ms9 MB + 80 KBAcceptedScore: 100

Subtask #1 Testcase #438.72 ms8 MB + 700 KBAcceptedScore: 0

Subtask #1 Testcase #513.2 us40 KBAcceptedScore: 0

Subtask #1 Testcase #612.69 us40 KBAcceptedScore: 0

Subtask #1 Testcase #712.43 us40 KBAcceptedScore: 0

Subtask #1 Testcase #883.348 ms18 MB + 216 KBAcceptedScore: 0

Subtask #1 Testcase #983.402 ms18 MB + 80 KBAcceptedScore: 0

Subtask #1 Testcase #1077.538 ms17 MB + 700 KBAcceptedScore: 0

Subtask #1 Testcase #1189.583 ms18 MB + 700 KBAcceptedScore: 0

Subtask #1 Testcase #1291.523 ms17 MB + 580 KBAcceptedScore: 0

Subtask #1 Testcase #1310.96 us40 KBAcceptedScore: 0


Judge Duck Online | 评测鸭在线
Server Time: 2024-04-25 06:19:50 | Loaded in 1 ms | Server Status
个人娱乐项目,仅供学习交流使用