QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#926778#618. 多项式乘法lwm77080 741ms134508kbC++172.7kb2025-03-06 11:34:502025-03-06 11:34:51

Judging History

This is the latest submission verdict.

  • [2025-03-06 11:34:51]
  • Judged
  • Verdict: 0
  • Time: 741ms
  • Memory: 134508kb
  • [2025-03-06 11:34:50]
  • Submitted

answer

#include <algorithm>
#include <cmath>
#include <complex>
#include <cstdint>
#include <ios>
#include <iostream>
#include <utility>
#include <vector>

template <typename T>
std::vector<T> fast_fourier_transform(
    const std::vector<T>& vec, std::int32_t inv, const std::vector<T>& rts
) {

    if (std::empty(vec)) {
        return std::vector<T>();
    }

    std::int32_t idx = 0;
    const std::int32_t sz = std::size(vec);
    std::vector vals = vec;

    for (std::int32_t i = 1; i < sz; ++i) {
        std::int32_t bit = sz >> 1;
        while (idx & bit) {
            idx ^= bit;
            bit >>= 1;
        }
        idx |= bit;
        if (i < idx) {
            std::swap(vals[i], vals[idx]);
        }
    }

    for (std::int32_t i = 2; i <= sz; i *= 2) {
        for (std::int32_t j = 0; j < sz; j += i) {
            T cur_rt(1);
            for (std::int32_t k = j; k < j + i / 2; ++k) {
                const T val_1 = vals[k];
                const T val_2 = vals[k + i / 2] * cur_rt;
                vals[k] = val_1 + val_2;
                vals[k + i / 2] = val_1 - val_2;
                cur_rt *= rts[__builtin_ctz(i)];
            }
        }
    }

    if (inv) {
        std::reverse(std::begin(vals) + 1, std::end(vals));
        const T inverse = T(1) / T(sz);
        for (auto& x : vals) {
            x *= inverse;
        }
    }

    return vals;

}

void solve() {

    using cmplx_t = std::complex<double>;

    static const double pi = std::acos(-1);

    std::int32_t m;
    std::int32_t n;

    std::cin >> n >> m;

    std::vector<cmplx_t> a(n + 1);

    for (auto& x : a) {
        std::int64_t coef;
        std::cin >> coef;
        x.real(coef);
    }

    std::vector<cmplx_t> b(m + 1);

    for (auto& x : b) {
        std::int64_t coef;
        std::cin >> coef;
        x.real(coef);
    }

    const std::int32_t lg = 31 - __builtin_clz((n + m + 1) * 2 - 1);

    std::vector<cmplx_t> rts(lg + 1);
    const std::int32_t sz = 1 << lg;

    for (std::int32_t i = 0; i <= lg; ++i) {
        rts[i] = std::polar(1.0, pi * 2 / (1 << i));
    }

    a.resize(sz);
    b.resize(sz);

    a = fast_fourier_transform(a, 0, rts);
    b = fast_fourier_transform(b, 0, rts);

    std::vector<cmplx_t> c(sz);

    for (std::int32_t i = 0; i < sz; ++i) {
        c[i] = a[i] * b[i];
    }

    c = fast_fourier_transform(c, 1, rts);

    for (std::int32_t i = 0; i <= n + m; ++i) {
        std::cout << std::lround(std::real(c[i])) << (i < n + m ? ' ' : '\n');
    }

}

int main() {

    std::cin.tie(nullptr);

    std::ios_base::sync_with_stdio(false);

    solve();

    return 0;

}

Details

Tip: Click on the bar to expand more detailed information

Pretests


Final Tests

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 3840kb

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 622165877277173760 1148384202335077376 1744330057081933824 1860706225583654912 2797555036758865920 2251669196605095936 2733962690963770368 2956161153011251200 3386689821974855680 4171909363448862720 3443615585976850432 3892200345118469120 4222713817313584128 4684195158345924608 46...

result:

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

Test #2:

score: 0
Wrong Answer
time: 3ms
memory: 4864kb

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:

134473066196336640 542666021981224960 904382502744817664 1309766133186756608 1350017506328969216 1550932542234263552 1748252215041064960 1784442257289969664 1696086725904924672 2047234800545726464 1943750560693878784 2719201956008656896 3192358180158537728 3385082672554606592 3552133728519356416 418...

result:

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

Test #3:

score: 0
Wrong Answer
time: 13ms
memory: 7636kb

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 168127330932752384 959380879566700544 803298356313980928 1575256237765296128 1528350212198236160 1729129109581201408 2670982502479298560 2072069917643898880 2609407488553385984 3183494412807176192 3065007322623901696 4107487645719330816 4220986909746266112 5187908787331661824 5048...

result:

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

Test #4:

score: 0
Wrong Answer
time: 58ms
memory: 19916kb

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:

462564226387410944 752354365912645632 817168649869590528 1159286506260529152 866250491030405120 1213131223354834944 1519025228769918976 1733602458821722112 2736704175792455680 2920908863843598336 3368153966425669632 3549256547316006912 2672722195493421056 3450543064709332992 3238543212086820864 3759...

result:

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

Test #5:

score: 0
Wrong Answer
time: 741ms
memory: 134508kb

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 762538095013789696 1119088241081843712 1110169788585345024 996699986919948288 1209671562135863296 1638544572592160768 1498679596894126080 1313292254537842688 1597672921025740800 2394882073769803776 1999652285474406400 2701355309770735616 2471104119067115520 2674231331998662656 370...

result:

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