Task: | A TIMES B! |
Sender: | aalto2024i_001 |
Submission time: | 2024-10-30 17:02:02 +0200 |
Language: | C++ (C++20) |
Status: | READY |
Result: | ACCEPTED |
test | verdict | time | |
---|---|---|---|
#1 | ACCEPTED | 0.00 s | details |
#2 | ACCEPTED | 0.00 s | details |
#3 | ACCEPTED | 0.00 s | details |
#4 | ACCEPTED | 0.00 s | details |
#5 | ACCEPTED | 0.00 s | details |
#6 | ACCEPTED | 0.00 s | details |
#7 | ACCEPTED | 0.00 s | details |
#8 | ACCEPTED | 0.00 s | details |
#9 | ACCEPTED | 0.00 s | details |
#10 | ACCEPTED | 0.00 s | details |
#11 | ACCEPTED | 0.00 s | details |
#12 | ACCEPTED | 0.00 s | details |
#13 | ACCEPTED | 0.00 s | details |
#14 | ACCEPTED | 0.00 s | details |
#15 | ACCEPTED | 0.00 s | details |
#16 | ACCEPTED | 0.00 s | details |
#17 | ACCEPTED | 0.00 s | details |
#18 | ACCEPTED | 0.00 s | details |
#19 | ACCEPTED | 0.00 s | details |
#20 | ACCEPTED | 0.00 s | details |
#21 | ACCEPTED | 0.00 s | details |
#22 | ACCEPTED | 0.00 s | details |
#23 | ACCEPTED | 0.00 s | details |
#24 | ACCEPTED | 0.00 s | details |
#25 | ACCEPTED | 0.00 s | details |
#26 | ACCEPTED | 0.00 s | details |
#27 | ACCEPTED | 0.00 s | details |
#28 | ACCEPTED | 0.00 s | details |
#29 | ACCEPTED | 0.00 s | details |
#30 | ACCEPTED | 0.00 s | details |
#31 | ACCEPTED | 0.00 s | details |
#32 | ACCEPTED | 0.00 s | details |
#33 | ACCEPTED | 0.00 s | details |
#34 | ACCEPTED | 0.00 s | details |
#35 | ACCEPTED | 0.00 s | details |
#36 | ACCEPTED | 0.00 s | details |
#37 | ACCEPTED | 0.00 s | details |
#38 | ACCEPTED | 0.00 s | details |
#39 | ACCEPTED | 0.00 s | details |
#40 | ACCEPTED | 0.00 s | details |
#41 | ACCEPTED | 0.00 s | details |
#42 | ACCEPTED | 0.00 s | details |
#43 | ACCEPTED | 0.00 s | details |
#44 | ACCEPTED | 0.00 s | details |
#45 | ACCEPTED | 0.00 s | details |
#46 | ACCEPTED | 0.00 s | details |
#47 | ACCEPTED | 0.00 s | details |
#48 | ACCEPTED | 0.00 s | details |
#49 | ACCEPTED | 0.00 s | details |
#50 | ACCEPTED | 0.00 s | details |
#51 | ACCEPTED | 0.00 s | details |
#52 | ACCEPTED | 0.00 s | details |
#53 | ACCEPTED | 0.00 s | details |
#54 | ACCEPTED | 0.00 s | details |
#55 | ACCEPTED | 0.00 s | details |
#56 | ACCEPTED | 0.07 s | details |
#57 | ACCEPTED | 0.07 s | details |
#58 | ACCEPTED | 0.07 s | details |
#59 | ACCEPTED | 0.07 s | details |
#60 | ACCEPTED | 0.07 s | details |
#61 | ACCEPTED | 0.64 s | details |
#62 | ACCEPTED | 0.64 s | details |
#63 | ACCEPTED | 0.64 s | details |
#64 | ACCEPTED | 0.63 s | details |
#65 | ACCEPTED | 0.63 s | details |
Compiler report
input/code.cpp: In function 'int main()': input/code.cpp:65:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result] 65 | scanf("%s%s", s1, s2); | ~~~~~^~~~~~~~~~~~~~~~
Code
#include<bits/stdc++.h> using namespace std; typedef long long LL; int read() { int x = 0, f = 1; char ch = getchar(); while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); } while (ch <= '9' && ch >= '0') { x = 10 * x + ch - '0'; ch = getchar(); } return x * f; } void print(int x) { if (x < 0) putchar('-'), x = -x; if (x >= 10) print(x / 10); putchar(x % 10 + '0'); } constexpr int N = 4000010, P = 998244353; int x1[N], x2[N], r[N]; char s1[N], s2[N]; int QuickPow(int x, int y) { int res(1); while (y) { if (y & 1) res = 1ll * res * x % P; x = 1ll * x * x % P; y >>= 1; } return res; } void NTT(int *x, int lim, int opt) { int i, j, k, m, gn, g, tmp; for (i = 0; i < lim; ++i) if (r[i] < i) swap(x[i], x[r[i]]); for (m = 2; m <= lim; m <<= 1) { k = m >> 1; gn = QuickPow(3, (P - 1) / m); for (i = 0; i < lim; i += m) { g = 1; for (j = 0; j < k; ++j, g = 1ll * g * gn % P) { tmp = 1ll * x[i + j + k] * g % P; x[i + j + k] = (x[i + j] - tmp + P) % P; x[i + j] = (x[i + j] + tmp) % P; } } } if (opt == -1) { reverse(x + 1, x + lim); int inv = QuickPow(lim, P - 2); for (i = 0; i < lim; ++i) x[i] = 1ll * x[i] * inv % P; } } int main() { // Test(); scanf("%s%s", s1, s2); int l1 = strlen(s1), l2 = strlen(s2); int lim = 1; while(lim < l1*2 || lim < l2*2) lim <<= 1; for(int i=0; i < l1; i++) x1[i] = s1[l1 - i - 1] - '0'; for(int i=0; i < l2; i++) x2[i] = s2[l2 - i - 1] - '0'; for (int i = 0; i < lim; ++i) r[i] = (i & 1) * (lim >> 1) + (r[i >> 1] >> 1); NTT(x1, lim, 1); NTT(x2, lim, 1); for (int i = 0; i < lim; ++i) x1[i] = 1ll * x1[i] * x2[i] % P; NTT(x1, lim, -1); int len(0); for (int i = 0; i < lim; ++i) { if (x1[i] >= 10) { len = i + 1; x1[i + 1] += x1[i] / 10; x1[i] %= 10; } if (x1[i]) len = max(len, i); } while (x1[len] >= 10) { x1[len + 1] += x1[len] / 10; x1[len] %= 10; len++; } for (int i = len; ~i; --i) putchar(x1[i] + '0'); }
Test details
Test 1
Verdict: ACCEPTED
input |
---|
8 5 |
correct output |
---|
40 |
user output |
---|
40 |
Test 2
Verdict: ACCEPTED
input |
---|
9 1 |
correct output |
---|
9 |
user output |
---|
9 |
Test 3
Verdict: ACCEPTED
input |
---|
9 5 |
correct output |
---|
45 |
user output |
---|
45 |
Test 4
Verdict: ACCEPTED
input |
---|
2 5 |
correct output |
---|
10 |
user output |
---|
10 |
Test 5
Verdict: ACCEPTED
input |
---|
8 7 |
correct output |
---|
56 |
user output |
---|
56 |
Test 6
Verdict: ACCEPTED
input |
---|
48 92 |
correct output |
---|
4416 |
user output |
---|
4416 |
Test 7
Verdict: ACCEPTED
input |
---|
1 40 |
correct output |
---|
40 |
user output |
---|
40 |
Test 8
Verdict: ACCEPTED
input |
---|
97 74 |
correct output |
---|
7178 |
user output |
---|
7178 |
Test 9
Verdict: ACCEPTED
input |
---|
58 8 |
correct output |
---|
464 |
user output |
---|
464 |
Test 10
Verdict: ACCEPTED
input |
---|
15 24 |
correct output |
---|
360 |
user output |
---|
360 |
Test 11
Verdict: ACCEPTED
input |
---|
4 7 |
correct output |
---|
28 |
user output |
---|
28 |
Test 12
Verdict: ACCEPTED
input |
---|
906 417 |
correct output |
---|
377802 |
user output |
---|
377802 |
Test 13
Verdict: ACCEPTED
input |
---|
778 105 |
correct output |
---|
81690 |
user output |
---|
81690 |
Test 14
Verdict: ACCEPTED
input |
---|
2 989 |
correct output |
---|
1978 |
user output |
---|
1978 |
Test 15
Verdict: ACCEPTED
input |
---|
2830 5329 |
correct output |
---|
15081070 |
user output |
---|
15081070 |
Test 16
Verdict: ACCEPTED
input |
---|
9 51382 |
correct output |
---|
462438 |
user output |
---|
462438 |
Test 17
Verdict: ACCEPTED
input |
---|
25053 71372 |
correct output |
---|
1788082716 |
user output |
---|
1788082716 |
Test 18
Verdict: ACCEPTED
input |
---|
258180 674616 |
correct output |
---|
174172358880 |
user output |
---|
174172358880 |
Test 19
Verdict: ACCEPTED
input |
---|
8821 2 |
correct output |
---|
17642 |
user output |
---|
17642 |
Test 20
Verdict: ACCEPTED
input |
---|
1742712 9600618 |
correct output |
---|
16731112196016 |
user output |
---|
16731112196016 |
Test 21
Verdict: ACCEPTED
input |
---|
8898606 2936506 |
correct output |
---|
26130809910636 |
user output |
---|
26130809910636 |
Test 22
Verdict: ACCEPTED
input |
---|
82670092 60138633 |
correct output |
---|
4971666322864236 |
user output |
---|
4971666322864236 |
Test 23
Verdict: ACCEPTED
input |
---|
54746871 83822602 |
correct output |
---|
4589025178578342 |
user output |
---|
4589025178578342 |
Test 24
Verdict: ACCEPTED
input |
---|
477252461 1032684 |
correct output |
---|
492850980435324 |
user output |
---|
492850980435324 |
Test 25
Verdict: ACCEPTED
input |
---|
5932935 379 |
correct output |
---|
2248582365 |
user output |
---|
2248582365 |
Test 26
Verdict: ACCEPTED
input |
---|
620114 3126641 |
correct output |
---|
1938873857074 |
user output |
---|
1938873857074 |
Test 27
Verdict: ACCEPTED
input |
---|
452757081 222748761 |
correct output |
---|
100851078826726641 |
user output |
---|
100851078826726641 |
Test 28
Verdict: ACCEPTED
input |
---|
689748332 888826746 |
correct output |
---|
613066765490487672 |
user output |
---|
613066765490487672 |
Test 29
Verdict: ACCEPTED
input |
---|
111337 25 |
correct output |
---|
2783425 |
user output |
---|
2783425 |
Test 30
Verdict: ACCEPTED
input |
---|
809 84435378 |
correct output |
---|
68308220802 |
user output |
---|
68308220802 |
Test 31
Verdict: ACCEPTED
input |
---|
9641697369926504411 425970950212942028697061039529... |
correct output |
---|
410708299033321711216812810174... |
user output |
---|
410708299033321711216812810174... |
Test 32
Verdict: ACCEPTED
input |
---|
793769623129909085108356241071... |
correct output |
---|
264404012608186879272715560773... |
user output |
---|
264404012608186879272715560773... |
Test 33
Verdict: ACCEPTED
input |
---|
8539777831492675800 436 |
correct output |
---|
3723343134530806648800 |
user output |
---|
3723343134530806648800 |
Test 34
Verdict: ACCEPTED
input |
---|
946492187160898604892390431179... |
correct output |
---|
585982368537725512535970251461... |
user output |
---|
585982368537725512535970251461... |
Test 35
Verdict: ACCEPTED
input |
---|
874046401974324184707688863838... |
correct output |
---|
174556202198322810668657866310... |
user output |
---|
174556202198322810668657866310... |
Test 36
Verdict: ACCEPTED
input |
---|
168584663428092347854539803060... |
correct output |
---|
235958453587245776929148968707... |
user output |
---|
235958453587245776929148968707... |
Test 37
Verdict: ACCEPTED
input |
---|
279013912031336395843652482056... |
correct output |
---|
856375236460411618343887929304... |
user output |
---|
856375236460411618343887929304... |
Test 38
Verdict: ACCEPTED
input |
---|
909594443312661242668561455177... |
correct output |
---|
801297086685128929836268694647... |
user output |
---|
801297086685128929836268694647... |
Test 39
Verdict: ACCEPTED
input |
---|
521558480102200460144622364590... |
correct output |
---|
403176935665359352292583479223... |
user output |
---|
403176935665359352292583479223... |
Test 40
Verdict: ACCEPTED
input |
---|
198766521920629467015839613580... |
correct output |
---|
197951285207558548760833360414... |
user output |
---|
197951285207558548760833360414... |
Test 41
Verdict: ACCEPTED
input |
---|
388239940637354291806784217812... |
correct output |
---|
354893636094929851749498258576... |
user output |
---|
354893636094929851749498258576... |
Test 42
Verdict: ACCEPTED
input |
---|
580031950564534684773525167998... |
correct output |
---|
225288306472433597677862095876... |
user output |
---|
225288306472433597677862095876... |
Test 43
Verdict: ACCEPTED
input |
---|
673497493525004204568833306269... |
correct output |
---|
104167516519697053781119530996... |
user output |
---|
104167516519697053781119530996... |
Test 44
Verdict: ACCEPTED
input |
---|
583582406474458495157747860432... |
correct output |
---|
355985267949419682046226194863... |
user output |
---|
355985267949419682046226194863... |
Test 45
Verdict: ACCEPTED
input |
---|
154401310284121033413839709675... |
correct output |
---|
472687322036571910421947159369... |
user output |
---|
472687322036571910421947159369... |
Test 46
Verdict: ACCEPTED
input |
---|
964784520177212016698 135881607827957154173561484162... |
correct output |
---|
131096471809203739325264543904... |
user output |
---|
131096471809203739325264543904... |
Test 47
Verdict: ACCEPTED
input |
---|
506417941420848908877158785176... |
correct output |
---|
124940484872553056181800567857... |
user output |
---|
124940484872553056181800567857... |
Test 48
Verdict: ACCEPTED
input |
---|
278205703909200971326699489015... |
correct output |
---|
213362541886605761113025837459... |
user output |
---|
213362541886605761113025837459... |
Test 49
Verdict: ACCEPTED
input |
---|
488919747667763730629078434642... |
correct output |
---|
244261035002054726047225565934... |
user output |
---|
244261035002054726047225565934... |
Test 50
Verdict: ACCEPTED
input |
---|
683013292533355268532590162229... |
correct output |
---|
271255985219635665074840248062... |
user output |
---|
271255985219635665074840248062... |
Test 51
Verdict: ACCEPTED
input |
---|
701382950383712289025758984281... |
correct output |
---|
396240397875971182850884660551... |
user output |
---|
396240397875971182850884660551... |
Test 52
Verdict: ACCEPTED
input |
---|
950530137216618089651057517232... |
correct output |
---|
525100658977646195130452101103... |
user output |
---|
525100658977646195130452101103... |
Test 53
Verdict: ACCEPTED
input |
---|
758180874616256083097058082046... |
correct output |
---|
612777382638418549100062437996... |
user output |
---|
612777382638418549100062437996... |
Test 54
Verdict: ACCEPTED
input |
---|
282198270649528096385750216226... |
correct output |
---|
878945962031578099916769892430... |
user output |
---|
878945962031578099916769892430... |
Test 55
Verdict: ACCEPTED
input |
---|
374271236006180996628555027124... |
correct output |
---|
205927043926518428842129271440... |
user output |
---|
205927043926518428842129271440... |
Test 56
Verdict: ACCEPTED
input |
---|
789860669365068182777748873091... |
correct output |
---|
369460448033120451265094062370... |
user output |
---|
369460448033120451265094062370... |
Test 57
Verdict: ACCEPTED
input |
---|
826700926013863385104801713448... |
correct output |
---|
291751287859134397942962144651... |
user output |
---|
291751287859134397942962144651... |
Test 58
Verdict: ACCEPTED
input |
---|
947468718382260248801518078140... |
correct output |
---|
226868697296935607336651841496... |
user output |
---|
226868697296935607336651841496... |
Test 59
Verdict: ACCEPTED
input |
---|
177252461103268440789803954968... |
correct output |
---|
111876380249200192763403085310... |
user output |
---|
111876380249200192763403085310... |
Test 60
Verdict: ACCEPTED
input |
---|
393293577943612353036749957226... |
correct output |
---|
336630505716557163667422969707... |
user output |
---|
336630505716557163667422969707... |
Test 61
Verdict: ACCEPTED
input |
---|
320114112664152374910455416563... |
correct output |
---|
136407754249269979820422504376... |
user output |
---|
136407754249269979820422504376... |
Test 62
Verdict: ACCEPTED
input |
---|
152757081122748761316522074282... |
correct output |
---|
107712372482584798763194835348... |
user output |
---|
107712372482584798763194835348... |
Test 63
Verdict: ACCEPTED
input |
---|
889748332988826746683887083103... |
correct output |
---|
729454517423131565738173030712... |
user output |
---|
729454517423131565738173030712... |
Test 64
Verdict: ACCEPTED
input |
---|
311337350148998951898280698942... |
correct output |
---|
245742878826375358332482490843... |
user output |
---|
245742878826375358332482490843... |
Test 65
Verdict: ACCEPTED
input |
---|
709744353788876782171034561202... |
correct output |
---|
198288295923437797210097622398... |
user output |
---|
198288295923437797210097622398... |