QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#5900#618. 多项式乘法Qingyu0 191ms95240kbC++175.2kb2021-01-27 18:54:362021-12-19 07:07:27

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:27]
  • 评测
  • 测评结果:0
  • 用时:191ms
  • 内存:95240kb
  • [2021-01-27 18:54:36]
  • 提交

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;
struct Complex
{
	long double x, y;
	Complex(long double x = 0, long double y = 0) : x(x), y(y) {}
};
Complex operator+(const Complex &u, const Complex &v) { return Complex(u.x + v.x, u.y + v.y); }
Complex operator-(const Complex &u, const Complex &v) { return Complex(u.x - v.x, u.y - v.y); }
Complex operator*(const Complex &u, const Complex &v) { return Complex(u.x * v.x - u.y * v.y, u.x * v.y + u.y * v.x); }

struct FFT
{
	int rev[N], len, k;
	const long double pi = acosl(-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(cosl(2.0 * pi / len), sinl(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(cosl(2.0 * pi * i / len), sinl(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(A._[i], 0.0);
	for (int i = 0; i <= d2; ++i) b[i] = Complex(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] = (long long)(c[i].x + 0.5) % mod;
	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: 30ms
memory: 67792kb

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:

683858405 5532908 499734644 910262433 221004060 924081859 392466244 64190191 260661827 939986124 283456705 260629527 990529005 704246439 991946825 236857596 903415179 900324872 938555807 225258166 874945427 516870324 74759448 769850102 353889933 300397175 63689546 115003947 872945381 407694645 918439557 365361053 166223370 -466025955 -466025955 -466025955 -466025955 -466025955 -466025955 -466025955 -466025955 -466025955 -466025955 -466025955 -466025955 -466025955 -466025955 -466025955 -466025955...

result:

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

Test #2:

score: 0
Wrong Answer
time: 30ms
memory: 67668kb

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:

700935872 677304021 772160877 479387844 109687663 263920077 29568067 960045863 636327734 585682990 409427618 14510839 441965355 92802190 551536992 216995952 59737006 790079646 55884192 796138836 265362280 66125516 150347723 93683594 205257061 672082054 86397651 573029951 541085645 293481633 905181460 745064401 450721601 554965715 176282644 539835231 212384125 210134031 327425476 419970354 763400179 -466025955 402503599 -466025955 -466025955 -466025955 -466025955 -466025955 556888546 -466025955 -...

result:

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

Test #3:

score: 0
Wrong Answer
time: 51ms
memory: 74808kb

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:

115266061 49822759 758685316 745755032 322992406 510572220 697418232 850654454 678357722 817660474 668537546 136612766 562893659 692804527 351392342 768364415 573248845 891136576 717296631 707934439 41738273 540703704 240728126 931260169 38727070 642515019 630807465 632184493 342949749 225410500 836271064 245406125 261143780 74492407 -466025955 -466025955 -466025955 -466025955 -466025955 -466025955 -466025955 -466025955 -466025955 -466025955 -466025955 -466025955 -466025955 -466025955 -466025955...

result:

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

Test #4:

score: 0
Wrong Answer
time: 191ms
memory: 95240kb

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:

821890226 646444730 701921472 744982894 891751268 338027782 134433819 686602044 653658254 704205943 763983972 160364404 773131240 630040620 467193486 675259382 824377470 394381137 870052261 473737392 246335911 372729342 656126194 677118861 890150618 374613244 160849048 144260219 450776422 646505961 937516356 316363815 449696873 -466025955 8647219 -466025955 -466025955 -466025955 -466025955 800554583 -466025955 -466025955 -466025955 -466025955 -466025955 -466025955 -466025955 -466025955 -46602595...

result:

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

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: