QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#342839#618. 多项式乘法jrjyy#0 133ms22800kbC++141.7kb2024-03-01 17:34:362024-03-01 17:34:37

Judging History

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

  • [2024-03-01 17:34:37]
  • 评测
  • 测评结果:0
  • 用时:133ms
  • 内存:22800kb
  • [2024-03-01 17:34:36]
  • 提交

answer

#include <bits/stdc++.h>

using i64 = long long;

using P = std::complex<long double>;

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

void dft(std::vector<P> &f, int rev) {
    const int n = int(f.size());
    assert((n & (n - 1)) == 0);
    std::vector<int> r(n);
    for (int i = 1; i < n; ++i) {
        r[i] = (r[i / 2] + i % 2 * n) / 2;
    }
    for (int i = 0; i < n; ++i) {
        if (r[i] < i) {
            std::swap(f[i], f[r[i]]);
        }
    }
    for (int l = 1; l < n; l *= 2) {
        P w(std::cos(2 * pi / l / 2), std::sin(2 * pi / l / 2 * rev));
        for (int p = 0; p < n; p += 2 * l) {
            P coef = 1;
            for (int i = p; i < p + l; ++i) {
                P t = f[i + l] * coef;
                f[i + l] = f[i] - t;
                f[i] = f[i] + t;
                coef *= w;
            }
        }
    }
    if (rev == -1) {
        for (int i = 0; i < n; ++i) {
            f[i] /= n;
        }
    }
}

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);

    int n, m;
    std::cin >> n >> m;
    ++n, ++m;

    std::vector<P> a(n);
    for (int i = 0; i < n; ++i) {
        int x;
        std::cin >> x;
        a[i] = x;
    }

    std::vector<P> b(m);
    for (int i = 0; i < m; ++i) {
        int x;
        std::cin >> x;
        b[i] = x;
    }

    const int k = 1 << std::__lg(2 * (n + m - 1) + 1);
    a.resize(k);
    b.resize(k);
    dft(a, 1);
    dft(b, 1);
    for (int i = 0; i < k; ++i) {
        a[i] *= b[i];
    }
    dft(a, -1);

    for (int i = 0; i < n + m - 1; ++i) {
        std::cout << i64(a[i].real() + 0.5) << " \n"[i == n + m - 1];
    }

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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:

293317256442960494 622165877277235061 1148384202335131335 1744330057081989176 1860706225583704207 2797555036758915605 2251669196605142438 2733962690963818294 2956161153011294051 3386689821974901456 4171909363448900859 3443615585976889647 3892200345118504644 4222713817313624301 4684195158345956888 46...

result:

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

Test #2:

score: 0
Wrong Answer
time: 9ms
memory: 4244kb

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:

134473066251752128 542666022105273258 904382502867748829 1309766133309789966 1350017506452048997 1550932542357696623 1748252215163956805 1784442257412371712 1696086726028547220 2047234800668045305 1943750560816803198 2719201956130676017 3192358180280723471 3385082672675316589 3552133728643161318 418...

result:

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

Test #3:

score: 0
Wrong Answer
time: 39ms
memory: 8088kb

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:

333096846126274048 168127337662618519 959380886286551056 803298363026089787 1575256244476093900 1528350218919665955 1729129116289528623 2670982509182381292 2072069924365216530 2609407495263965473 3183494419510144929 3065007329336389977 4107487652426999416 4220986916461154036 5187908794044089813 5048...

result:

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

Test #4:

score: 0
Wrong Answer
time: 133ms
memory: 22800kb

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:

462564215091239936 752354318999391151 817168602923644922 1159286459415537390 866250444175613985 1213131176434711460 1519025181823655642 1733602411953004600 2736704129104248281 2920908816975636628 3368153919546466923 3549256500545570609 2672722148554810932 3450543017845175907 3238543165182986251 3759...

result:

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

Test #5:

score: 0
Time Limit Exceeded

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:

208919995550834688 762534323350482851 1119084467160744518 1110166013565154391 996696216066967275 1209667788976703879 1638540798209378017 1498675823697336946 1313288482304689528 1597669149236361166 2394878301005128061 1999648511231700606 2701351538559352692 2471100346917996603 2674227557866342154 370...

result: