QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#340589#618. 多项式乘法KevinLikesCoding#0 517ms137016kbC++141.8kb2024-02-29 10:32:172024-02-29 10:32:18

Judging History

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

  • [2024-02-29 10:32:18]
  • 评测
  • 测评结果:0
  • 用时:517ms
  • 内存:137016kb
  • [2024-02-29 10:32:17]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define FOR(i,n,m) for(int i=(n);i<=(m);i++)
#define ROF(i,n,m) for(int i=(n);i>=(m);i--)
#define REP(i,n) for(int i=0;i<(n);i++)
#define SZ(v) v.size()
#define pb push_back
template < typename A , typename B>
inline bool chmax(A &x, B y) { return (x < y ? (x = y, true) : false); }
template < typename A , typename B>
inline bool chmin(A &x, B y) { return (x > y ? (x = y, true) : false); }
const int N = 1e6 + 5;
const double PI = acos(-1.);
int n, m;
struct cp {
	double x, y;
	cp(double x = 0, double y = 0): x(x), y(y) {}
	cp operator + (cp A) { return cp(x + A.x, y + A.y); }
	cp operator - (cp A) { return cp(x - A.x, y - A.y); }
	cp operator * (cp A) { return cp(x * A.x - y * A.y, x * A.y + y * A.x); }
};
int r[N << 2];
cp f[N << 2], g[N << 2];
void FFT(cp *a, int lim, int opt) {
	REP(i, lim) {
		if(i < r[i]) swap(a[i], a[r[i]]);
	}
	for(int i = 1; i < lim; i <<= 1) {
		cp wn(cos(PI / i), opt * sin(PI / i));
		for(int j = 0; j < lim; j += (i << 1)) {
			cp w(1, 0);
			for(int k = 0; k < i; k++, w = w * wn) {
				cp x = a[j + k];
				cp y = a[j + k + i] * w;
				a[j + k] = x + y;
				a[j + k + i] = x - y;
			}
		}
	}
	if(opt == 1) return;
	REP(i, lim) {
		a[i].x /= lim;
	}
}
void solve() {
	cin >> n >> m;
	FOR(i, 0, n) {
		ll x; cin >> x;
		f[i] = cp(x, 0);
	}
	FOR(i, 0, m) {
		ll x; cin >> x;
		g[i] = cp(x, 0);
	}
	int lim = 1, l = 0;
	while(lim <= (n + m)) lim <<= 1, l++;
	REP(i, lim) r[i] = (r[i >> 1] >> 1) | ((i & 1) << (l - 1)); 
	FFT(f, lim, 1);
	FFT(g, lim, 1);
	REP(i, lim) f[i] = f[i] * g[i];
	FFT(f, lim, -1);
	FOR(i, 0, n + m) {
		cout << (ll)(f[i].x + 0.5) << " ";
	}
	cout << endl;
}
int main() {
	ios :: sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	solve();
	return 0;
}

详细

Test #1:

score: 0
Wrong Answer
time: 7ms
memory: 128908kb

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 57138...

output:

293317256442939392 622165877277214080 1148384202335116672 1744330057081969920 1860706225583684608 2797555036758894592 2251669196605124352 2733962690963800576 2956161153011274240 3386689821974882304 4171909363448884224 3443615585976872448 3892200345118491136 4222713817313602560 4684195158345940992 46...

result:

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

Test #2:

score: 0
Wrong Answer
time: 24ms
memory: 128900kb

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 53579...

output:

134473066196303872 542666022050037952 904382502812372096 1309766133254808576 1350017506397015808 1550932542302759936 1748252215108783872 1784442257357656320 1696086725973108480 2047234800613170176 1943750560761675520 2719201956076039680 3192358180225939968 3385082672620725248 3552133728588163584 418...

result:

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

Test #3:

score: 0
Wrong Answer
time: 32ms
memory: 129068kb

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 3...

output:

333096843327045632 168127334864995200 959380883493882880 803298360237551616 1575256241681380608 1528350216118044672 1729129113495165184 2670982506394829312 2072069921566100736 2609407492469098496 3183494416717645824 3065007326546564096 4107487649631825408 4220986913661903872 5187908791253966848 5048...

result:

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

Test #4:

score: 0
Wrong Answer
time: 68ms
memory: 129872kb

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...

output:

462564226388459520 752354330290595200 817168614222064640 1159286470716533248 866250455480138368 1213131187714291968 1519025193116198144 1733602423241587712 2736704140389190656 2920908828248784896 3368153930840932352 3549256511840564736 2672722159855393280 3450543029128673792 3238543176477613568 3759...

result:

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

Test #5:

score: 0
Wrong Answer
time: 517ms
memory: 137016kb

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 ...

output:

208921535912607744 762535863796228224 1119086009711107840 1110167556474648192 996697756038773504 1209669330082332160 1638542341049849600 1498677366199349248 1313290022750608640 1597670690038590720 2394879843312002048 1999650054339282432 2701353078574606336 2471101887991214080 2674229100689739776 370...

result:

wrong answer 1st numbers differ - expected: '199012842', found: '208921535912607744'