QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#5899#618. 多项式乘法Qingyu0 71ms51844kbC++175.3kb2021-01-27 18:51:522021-12-19 07:07:24

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2021-12-19 07:07:24]
  • 评测
  • 测评结果:0
  • 用时:71ms
  • 内存:51844kb
  • [2021-01-27 18:51:52]
  • 提交

answer

#include <bits/stdc++.h>

const int N = 1e6 + 50;
const int mod = 998244353;
const int g = 3;

inline int inc(int x, int y) { x += y - mod; return x + (x >> 31 & mod); }
inline int dec(int x, int y) { x -= y; return x + (x >> 31 & mod); }
inline int mul(int x, int y) { return 1ll * x * y % mod; }
inline int fastpow(int x, int p)
{
	int r = 1;
	while (p)
	{
		if (p & 1) r = mul(r, x);
		x = mul(x, x);
		p >>= 1;
	}
	return r;
}

struct NTT
{
	int omega[N], omegaInv[N], rev[N], len, k;
	inline void init(int n)
	{
		len = 1, k = 0;
		while (len <= n) len <<= 1, ++k;
		for (int i = 0; i < len; ++i) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (k - 1));
		const int t = fastpow(g, (mod - 1) / len);
		omega[0] = omegaInv[0] = 1;
		for (int i = 1; i < len; ++i) omega[i] = omegaInv[len - i] = mul(omega[i - 1], t);
	}
	inline void DFT(int *a, const int *w)
	{
		for (int i = 1; i < len; ++i) if (i < rev[i]) std::swap(a[i], a[rev[i]]);
		for (int h = 1; h < len; h <<= 1)
			for (int t = len / (h << 1), j = 0; j < len; j += (h << 1))
			{
				const int *wn = w; int *x = a + j, *y = a + j + h;
				for (int i = j; i < j + h; ++i)
				{
					int _1 = *x, _2 = mul(*y, *wn);
					*x++ = inc(_1, _2);
					*y++ = dec(_1, _2);
					wn += t;
				}
			}
		if (w == omegaInv)
		{
			const int t = mod - (mod - 1) / len;
			for (int i = 0; i < len; ++i) a[i] = mul(a[i], t);
		}
	}
	inline void operator()(std::vector<int> &_, int op)
	{
		if (_.size() < len) _.resize(len);
		if (op == 1) DFT(_.data(), omega);
		else DFT(_.data(), omegaInv);
		assert(_.size() >= len);
	}
} ntt;

template<typename T = double> struct Complex
{
	T x, y;
	Complex(T x = 0, T y = 0) : x(x), y(y) {}
};
template<typename T> Complex<T> operator+(const Complex<T> &u, const Complex<T> &v) { return Complex<T>(u.x + v.x, u.y + v.y); }
template<typename T> Complex<T> operator-(const Complex<T> &u, const Complex<T> &v) { return Complex<T>(u.x - v.x, u.y - v.y); }
template<typename T> Complex<T> operator*(const Complex<T> &u, const Complex<T> &v) { return Complex<T>(u.x * v.x - u.y * v.y, u.x * v.y + u.y * v.x); }

struct FFT
{
	int rev[N], len, k;
	const double pi = acos(-1.0);
	Complex<> omega[N], omegaInv[N];	
	inline void init(int n)
	{
		len = 1, k = 0;
		while (len <= n) len <<= 1, ++k;
		for (int i = 0; i < len; ++i) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (k - 1));
		Complex t(cos(2.0 * pi / len), sin(2.0 * pi / len));
		omega[0] = omegaInv[0] = Complex(1.0, 0.0);
		for (int i = 1; i < len; ++i) 
			if (i & 32) omega[i] = omegaInv[len - i] = omega[i - 1] * t;
			else omega[i] = omegaInv[len - i] = Complex(cos(2.0 * pi * i / len), sin(2.0 * pi * i / len));

	}
	inline void DFT(Complex<> *a, const Complex<> *w)
	{
		for (int i = 1; i < len; ++i) if (i < rev[i]) std::swap(a[i], a[rev[i]]);
		for (int h = 1; h < len; h <<= 1)
			for (int t = len / (h << 1), j = 0; j < len; j += (h << 1))
			{
				const Complex<> *wn = w; Complex<> *x = a + j, *y = a + j + h;
				for (int i = j; i < j + h; ++i)
				{
					Complex<> _1 = *x, _2 = *y * *wn;
					*x++ = _1 + _2;
					*y++ = _1 - _2;
					wn += t;
				}
			}
		if (w == omegaInv)
		{
			for (int i = 0; i < len; ++i) a[i].x /= len;
		}
	}
	inline void operator()(std::vector<Complex<>> &_, int op)
	{
		if (_.size() < len) _.resize(len);
		if (op == 1) DFT(_.data(), omega);
		else DFT(_.data(), omegaInv);
		assert(_.size() >= len);
	}
} fft;

struct Poly
{
	std::vector<int> _;
	Poly(){}
	Poly(const std::vector<int> &_) : _(_) {}
	inline int& operator[](int k)
	{
		if (_.size() <= k) _.resize(k + 1);
		return _[k];
	}
	inline int operator[](int k) const
	{
		if (_.size() <= k) return 0;
		return _[k];
	}
	inline int deg() const
	{
		return (int)_.size() - 1;
	}
};

template <int T>
struct fast_io
{
	char p[T], q[T], * p1, * p2, * q1, * q2;
	fast_io()
	{
		p1 = p2 = p;
		q1 = q, q2 = q + T;
	}
	inline char gc()
	{
		return p1 == p2 && (p2 = (p1 = p) + fread(p, 1, T, stdin), p1 == p2) ? EOF : *p1++;
	}
	inline void pc(char c)
	{
		if (q1 == q2) q2 = (q1 = q) + fwrite(q, 1, T, stdout);
		*q1++ = c;
	}
	~fast_io()
	{
		fwrite(q, 1, q1 - q, stdout);
	}
};
fast_io<1 << 20> io;
inline int read()
{
	int res = 0;
	char ch;
	do ch = io.gc(); while (ch < 48 || ch > 57);
	do res = res * 10 + ch - 48, ch = io.gc(); while (ch >= 48 && ch <= 57);
	return res;
}
inline void put(int64_t x)
{
	if (x < 0) io.pc('-'), x = -x;
	if (x >= 10) put(x / 10);
	io.pc(48 + x % 10);
}
inline void output(int64_t x, char ch = ' ')
{
	put(x);
	io.pc(ch);
}

inline Poly operator*(const Poly &A, const Poly &B)
{
	int d1 = A.deg(), d2 = B.deg();
	fft.init(d1 + d2 + 1);
	std::vector<Complex<>> a(fft.len), b(fft.len), c(fft.len);
	for (int i = 0; i <= d1; ++i) a[i] = Complex<double>(A._[i], 0.0);
	for (int i = 0; i <= d2; ++i) b[i] = Complex<double>(B._[i], 0.0);
	fft(a, 1), fft(b, 1);
	for (int i = 0; i < fft.len; ++i) c[i] = a[i] * b[i];
	fft(c, -1);
	std::vector<int> d(d1 + d2 + 1);
	for (int i = 0; i <= d1 + d2; ++i) d[i] = (c[i].x + 0.5);
	return Poly(d);
}
int main()
{
	Poly A, B;
	int n = read(), m = read();
	for (int i = 0; i <= n; ++i) A[i] = read();
	for (int i = 0; i <= m; ++i) B[i] = read();
	Poly C = A * B;
	for (int i = 0; i <= n + m; ++i) output(C[i]);
	return 0;
}

詳細信息

Test #1:

score: 0
Wrong Answer
time: 4ms
memory: 36248kb

input:

96 96
600395131 184265451 942971382 534262851 830366882 542271170 294355449 501371170 797809599 964826049 276651245 375755165 662619442 941920605 328216963 507795473 460271147 874920847 818231910 156789488 590591583 732194508 793983630 93566697 836155866 305319153 432040686 621119061 835023373 571381805 907090013 2182462 302915289 855760137 453034423 194501808 602679162 754637041 43020929 280523649 563297193 586403321 953313978 846966649 939322157 224782218 423578586 553034359 236753930 97579416...

output:

-2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483...

result:

wrong answer 1st numbers differ - expected: '683858396', found: '-2147483648'

Test #2:

score: 0
Wrong Answer
time: 4ms
memory: 37816kb

input:

4992 4994
471194390 313639917 705341086 119536186 430124603 244978845 185588341 13731324 707132801 88167972 927324568 846658454 523684029 5133605 767200778 502476309 539772401 778154025 266136872 183516351 260704325 49303370 475056182 928574546 740424153 277920667 708439854 746983628 839491869 53579512 244429021 50734540 136957850 76303465 579487379 368990885 163226387 580415257 208768433 19113590 223054273 551672113 124853857 40273596 563383965 193659125 125299959 606009066 177398857 298766403 ...

output:

-2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483...

result:

wrong answer 1st numbers differ - expected: '700935456', found: '-2147483648'

Test #3:

score: 0
Wrong Answer
time: 28ms
memory: 39716kb

input:

29995 29992
417238081 53580806 733071257 224121793 786137422 127072245 129083351 988357079 246853229 150935424 596994106 975796660 838029970 619117898 328485797 948485083 574261409 79312345 596346086 489787404 929520168 515647000 211731260 50868568 811515357 428215135 498099163 644485329 802849075 323480593 82977609 981158224 146168797 843709970 940251244 748340642 715098449 135717736 386164511 936195593 287388374 780056143 263853402 955329298 295993331 384883174 985705100 42684143 46671610 3591...

output:

-2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483...

result:

wrong answer 1st numbers differ - expected: '115270920', found: '-2147483648'

Test #4:

score: 0
Wrong Answer
time: 71ms
memory: 51844kb

input:

100000 99993
812398607 947396010 797321381 883949986 56052416 586258761 193247973 611124334 773505112 142179482 565466227 140875825 79890768 893500101 553768089 648879319 480419657 915530184 799329430 494818755 793895824 851865180 459534006 259473419 610037701 472768430 868914058 887444584 588850309 931042551 140500440 113474012 799450889 774662643 30955294 500108316 30652117 259096565 434687860 315020281 896443850 55195632 961583298 802194511 161293453 553381027 902400419 795643835 692301037 85...

output:

-2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483...

result:

wrong answer 1st numbers differ - expected: '821875273', found: '-2147483648'

Test #5:

score: 0
Runtime Error

input:

999993 999994
388529697 811245378 165909114 295553883 667981275 78502012 400874009 139394758 249494489 4636487 997712665 259780805 431039016 716944209 709300152 356513646 823185021 699568300 650937921 859190797 899514799 785648601 933470757 627225124 349752104 471458923 456404256 48134357 315599086 833579801 571765596 992347138 98921603 132574566 124250140 864032331 752503099 921369464 868713168 689411883 275126498 61746579 230876576 589241003 500341687 478442921 800494882 561661108 319422304 38...

output:


result: