QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#5901#618. 多项式乘法Qingyu0 161ms95156kbC++175.1kb2021-01-27 18:55:352021-12-19 07:07:31

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:31]
  • 评测
  • 测评结果:0
  • 用时:161ms
  • 内存:95156kb
  • [2021-01-27 18:55:35]
  • 提交

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) 
			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: 8ms
memory: 67204kb

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:

683858397 5532889 499734625 910262422 221004047 924081845 392466234 64190177 260661818 939986112 283456694 260629519 990528997 704246432 991946818 236857591 903415174 900324864 938555802 225258158 874945421 516870318 74759446 769850099 353889932 300397174 63689541 115003947 872945380 407694643 918439556 365361055 166223372 -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: '683858397'

Test #2:

score: 0
Wrong Answer
time: 25ms
memory: 68720kb

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:

700935600 677303397 772160333 479387363 109687118 263919516 29567682 960045477 636327269 585682620 409427073 14510422 441964938 92801884 551536590 216995565 59736652 790079322 55883949 796138529 265361877 66125098 150347416 93683271 205256689 672081681 86397311 573029707 541085337 293481356 905181232 745064077 450721310 554965372 176282285 539834905 212383880 210133786 327425199 419970044 763399870 -466025955 402503145 -466025955 -466025955 -466025955 -466025955 -466025955 556888267 -466025955 -...

result:

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

Test #3:

score: 0
Wrong Answer
time: 41ms
memory: 74928kb

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:

115271181 49834535 758695556 745765017 323001366 510581181 697426680 850661623 678365148 817669948 668545738 136620449 562901341 692812210 351399255 768371075 573255248 891145284 717304825 707941355 41744932 540710876 240734272 931266574 38733219 642522192 630813358 632189618 342955386 225416137 836276187 245410481 261148907 74500353 -466025955 -466025955 -466025955 -466025955 -466025955 -466025955 -466025955 -466025955 -466025955 -466025955 -466025955 -466025955 -466025955 -466025955 -466025955...

result:

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

Test #4:

score: 0
Wrong Answer
time: 161ms
memory: 95156kb

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:

821881010 646417593 701900991 744962412 891732835 338008324 134417433 686588730 653643915 704188530 763969632 160348529 773116900 630028328 467183240 675246066 824368249 394361673 870036383 473725095 246325150 372716534 656112875 677109638 890141393 374598897 160837261 144248945 450769245 646495198 937507642 316353053 449688159 -466025955 8630822 -466025955 -466025955 -466025955 -466025955 800542795 -466025955 -466025955 -466025955 -466025955 -466025955 -466025955 -466025955 -466025955 -46602595...

result:

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

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: