QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#6664#621. 多项式指数函数little_sun0 134ms20196kbC++205.6kb2021-03-08 16:16:062021-12-19 09:22:24

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 09:22:24]
  • 评测
  • 测评结果:0
  • 用时:134ms
  • 内存:20196kb
  • [2021-03-08 16:16:06]
  • 提交

answer

#include <bits/stdc++.h>

#define R register
#define ll unsigned long long
#define meow(cat...) fprintf(stderr, cat)
#define sum(a, b, mod) (((a) + (b)) % mod)

const int G = 3;
const int inv2 = 499122177;
const int MaxN = 1e6 + 10;
const int mod = 998244353;

int n, k, lim, w[MaxN], rev[MaxN], _inv[MaxN];

void Mod(int &x) { x += x >> 31 & mod; }

void __init()
{
    _inv[1] = 1;
    for (int i = 2; i < MaxN; i++)
        _inv[i] = (ll)(mod - mod / i) * _inv[mod % i] % mod;
}

int fast_pow(int a, int b)
{
    int ret = 1;
    while (b)
    {
        if (b & 1)
            ret = (ll)ret * a % mod;
        a = (ll)a * a % mod, b >>= 1;
    }
    return ret;
}

void init(int n)
{
    int l = 32 - __builtin_clz(n - 1);
    lim = (1 << l);
    for (int i = 0, ri = 0; i < lim; i++)
    {
        rev[i] = ri;
        for (int k = lim >> 1; (ri ^= k) < k;)
            k >>= 1;
    }
    int wn = fast_pow(G, (mod - 1) >> l);
    w[lim >> 1] = 1;
    for (int i = (lim >> 1) + 1; i < lim; i++)
        w[i] = (ll)w[i - 1] * wn % mod;
    for (int i = (lim >> 1) - 1; i; --i)
        w[i] = w[i << 1];
    lim = l;
}

struct poly
{
    std::vector<int> v;

    inline poly() {}
    inline poly(int n) : v(n) {}
    inline poly(const poly &r) : v(r.v) {}
    inline poly(const std::vector<int> &r) : v(r) {}

    inline size_t size() { return v.size(); }
    inline bool empty() { return v.empty(); }
    inline void resize(int n) { v.resize(n); }
    inline void clear() { v.clear(); }
    inline void shl() { v.insert(v.begin(), 0); }
    void shrink()
    {
        while (!v.empty() && !v.back())
            v.pop_back();
    }

    inline int &operator[](int i) { return v[i]; }
    inline static int len(int n) { return 1 << (32 - __builtin_clz(n - 1)); }

    void deriv()
    {
        for (int i = 1; i < v.size(); i++)
            v[i - 1] = (ll)i * v[i] % mod;
        v.pop_back();
    }
    void intg()
    {
        shl();
        for (int i = 1; i < v.size(); i++)
            v[i] = (ll)v[i] * _inv[i] % mod;
    }

    void dft(int n)
    {
        static ll tmp[MaxN];
        int ofs = lim - __builtin_ctz(n);
        resize(n);
        if (n <= 1) return;
        for (int i = 0; i < n; i++)
            tmp[rev[i] >> ofs] = v[i];
        for (int i = 0; i < n; i += 2)
        {
            int x = tmp[i], y = tmp[i + 1];
            tmp[i] = x + y, tmp[i + 1] = x + mod - y;
        }
        for (int i = 2; i < n; i <<= 1)
            for (int j = 0; j < n; j += (i << 1))
                for (int k = 0; k < i; ++k)
                {
                    int y = (ll)tmp[i + j + k] * w[i + k] % mod;
                    tmp[i + j + k] = tmp[j + k] + mod - y, tmp[j + k] += y;
                }
        for (int i = 0; i < n; i++)
            v[i] = tmp[i] % mod;
    }
    void idft(int n)
    {
        dft(n);
        if (n <= 1) return;
        std::reverse(v.begin() + 1, v.end());
        int tmp = mod - (mod - 1) / n;
        for (int i = 0; i < n; i++)
            v[i] = (ll)v[i] * tmp % mod;
    }
    void mul(poly r)
    {
        int n = len(size() + r.size() - 1);
        dft(n), r.dft(n);
        for (int i = 0; i < n; i++)
            v[i] = (ll)v[i] * r[i] % mod;
        idft(n), shrink();
    }
    void inv()
    {
        std::vector<int> va(1);
        int n = size(), m = len(n);
        va[0] = fast_pow(v[0], mod - 2);
        poly a; v.resize(m), v.swap(va);
        for (int i = 1; i <= m; i <<= 1)
        {
            a.resize(i);
            for (int j = 0; j < i; j++)
                a[j] = va[j];
            a.dft(i << 1), dft(i << 1);
            for (int j = 0; j < (i << 1); j++)
                v[j] = v[j] * (2 + mod - (ll)v[j] * a[j] % mod) % mod;
            idft(i << 1), resize(i);
        }
        resize(n);
    }
    void ln()
    {
        poly f0 = *this;
        int n = size();
        deriv(), f0.inv(), mul(f0);
        resize(n), intg(), resize(n);
    }
    void exp()
    {
        std::vector<int> va(1);
        va[0] = 1; poly a;
        int n = size(), m = len(n);
        v.resize(m), v.swap(va);
        for (int i = 1; i <= m; i *= 2)
        {
            a = *this, a.resize(i), a.ln();
            for (int j = 0; j < i; j++)
                a[j] = (va[j] + !j + mod - a[j]) % mod;
            mul(a), resize(i);
        }
        resize(n);
    }
    void pw(int k)
    {
        ln();
        for (int i = 0; i < n; i++)
            v[i] = (ll)v[i] * k % mod;
        exp();
    }
    void sqrt()
    {
        std::vector<int> va(1);
        int n = size(), m = len(n);
        poly a, b; va[0] = 1;
        v.resize(m), v.swap(va);
        for (int i = 1; i <= m; i <<= 1)
        {
            a.resize(i << 1), b.resize(i << 1);
            for (int j = 0; j < i; j++)
                a[j] = va[j], b[j] = v[j];
            b.inv(), a.mul(b);
            for (int j = 0; j < (i << 1); j++)
                v[j] = (ll)(v[j] + a[j]) % mod * inv2 % mod;
            resize(i);
        }
        resize(n);
    }
} a;

inline int read()
{
    ll x = 0;
    char ch = getchar();
    while (ch > '9' || ch < '0')
        ch = getchar();
    while (ch <= '9' && ch >= '0')
        x = ((x * 10) + (ch ^ 48)) % mod, ch = getchar();
    return x;
}

signed main()
{
    n = read(), __init();
    a.resize(n), init(n * 2);
    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);
    a.exp();
    for (int i = 0; i < n; i++)
        printf("%d ", a[i]);
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Runtime Error

input:

100
0 158447743 737554986 671332600 489297184 754299210 115728600 816221630 819073359 691660913 910093246 562505672 355119917 385019894 611338034 123976316 122342952 82142434 796101450 994778874 575255638 493217967 652609142 662045597 783871340 470398790 241710709 754059035 534582325 836438174 957893067 584407346 640541600 410035922 84171732 175013006 606606840 773798688 469639368 144082552 758959232 657846445 877015573 456859086 388014168 518816564 674332059 227983790 428743727 438581021 222389...

output:


result:


Test #2:

score: 0
Wrong Answer
time: 8ms
memory: 13172kb

input:

5000
0 354399910 26360255 630255958 717224815 366941345 333979504 905420494 38176634 475666562 611197455 433060682 509600868 845217181 520468365 529689763 431747498 192834976 685184103 287994809 273221518 522219732 427553800 10872482 525061651 448069946 183539744 610476003 840167561 241104955 404100586 905579642 619539314 759291945 841403216 335674561 812589295 739329439 436504205 457028593 882959179 173954181 530617359 285120636 874807613 623774085 659212492 947769439 351309346 244743499 453523...

output:

455830319 979801270 832488958 66979870 162008991 263560082 445270859 694594408 243842776 928254294 904020458 368576062 377523444 687948385 187378686 667609994 72601002 863054000 305643322 386810020 662786835 45534599 853562025 85839763 44157834 195824077 504475563 952295867 13954618 90111066 920090775 626718701 670776683 715905620 215876439 628089606 512609011 280397255 799269706 6550333 967122761 251227843 30375212 54115178 428792634 923358596 654741799 968578711 794419515 353424617 414589162 2...

result:

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

Test #3:

score: 0
Wrong Answer
time: 40ms
memory: 18752kb

input:

30000
0 147199510 293972908 780683378 633744119 800282266 162025013 919460711 939176222 298044997 277962122 729446209 455723129 756791462 84697115 579989768 945113433 549318980 229266945 869577376 103161009 960973464 440149102 836285074 687333626 638404974 184096947 370164754 454531549 142629528 150136518 257960790 158701904 511542041 393663496 771954923 878900233 618098281 645781345 282407187 177883451 71013292 201053861 290140489 414256579 859623839 225235471 541514087 973378894 661254664 9601...

output:

455830319 180985219 930800801 555123436 306429720 127204836 615558557 324154393 970241854 776470518 401241336 625831534 612322453 334668087 188397191 791515272 311909753 957558521 37432 244507979 566275698 177119956 489034877 816082015 44412012 845939672 606793543 33986650 52785596 336111241 659444525 262659022 707252798 119753690 938085963 54203265 384624418 119647677 204907433 395208856 70632764 954475981 572021193 109502655 414723628 215312999 80201721 463336136 212099720 608645063 651138575 ...

result:

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

Test #4:

score: 0
Wrong Answer
time: 134ms
memory: 20196kb

input:

100000
0 279349013 196667718 617497154 78288698 996674429 180463729 304956112 173800460 352061138 224505321 119706982 726737325 564797383 757014824 888433954 747100108 723246918 645172013 184990722 321964667 456686646 138153830 701558524 317746193 650472945 49496183 864461799 982372868 582778782 242264290 885892104 738219036 281176547 57656491 78806101 218302501 307656256 981707358 893325626 285028204 670805979 780203944 868002994 665180137 173048965 901701985 859037831 56668037 446632049 105548...

output:

455830319 510995400 659116652 932876881 107104596 431855 683473935 610605821 400517197 69971724 111515941 69353349 892252291 418135838 973847542 334949163 531672521 811871832 668096551 653243671 207835792 860087865 513332120 612470782 51265770 294376239 286771454 210098555 187113268 707073464 564637420 102513146 643002416 760055861 677496826 78921850 756158093 246045901 948954758 69632967 274717679 527164792 210087927 376884444 537383198 588910928 450281257 838689224 665891757 886226562 83653176...

result:

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

Test #5:

score: 0
Time Limit Exceeded

input:

1000000
0 204517192 162156394 729093416 352181074 335898409 357987855 386581690 26622360 437289663 34104646 938411413 659876244 293619518 291093969 909364118 179765868 89417259 632261731 375051702 493701794 771716785 682264158 329653513 86558030 9195128 957504298 22555222 384175297 128022431 595744458 181498790 672338926 479510752 420389346 652086132 134440599 263340995 500647786 721266545 21205425 522098385 546869280 418858420 804140401 347071725 717515538 26493457 742389665 501200675 718700801...

output:


result: