QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#465863#621. 多项式指数函数chroneZ#0 1695ms89052kbC++174.7kb2024-07-07 12:19:062024-07-07 12:19:06

Judging History

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

  • [2024-07-07 12:19:06]
  • 评测
  • 测评结果:0
  • 用时:1695ms
  • 内存:89052kb
  • [2024-07-07 12:19:06]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

constexpr int mod = 998244353, N = 1 << 22, invg = (mod + 1) / 3;
namespace basic {
  inline int add(int x, int y) {return (x + y >= mod ? x + y - mod : x + y);}
  inline int dec(int x, int y) {return (x - y < 0 ? x - y + mod : x - y);}
  inline void ad(int &x, int y) {x = add(x, y);}
  inline void de(int &x, int y) {x = dec(x, y);}

  inline int qpow(int a, int b) {
    int r = 1;
    while(b) {
      if(b & 1) r = 1ll * r * a % mod;
      a = 1ll * a * a % mod; b >>= 1;
    }
    return r;
  }
  inline int inv(int x) {return qpow(x, mod - 2);}

  int fac[N], ifac[N];
  inline void fac_init(int n = N - 1) {
    fac[0] = 1;
    for(int i = 1; i <= n; i++)
      fac[i] = 1ll * fac[i - 1] * i % mod;
    ifac[n] = inv(fac[n]);
    for(int i = n - 1; i >= 0; i--)
      ifac[i] = 1ll * ifac[i + 1] * (i + 1) % mod;
  }
  int invx[N];
  inline void inv_init(int n = N - 1) {
    invx[1] = 1;
    for(int i = 2; i <= n; i++)
      invx[i] = 1ll * (mod - mod / i) * invx[mod % i] % mod;
  }
  inline int binom(int n, int m) {
    if(n < m || m < 0) return 0;
    return 1ll * fac[n] * ifac[m] % mod * ifac[n - m] % mod;
  }
  int rev[N];
  inline void rev_init(int n) {
    for(int i = 1; i < n; i++) {
      rev[i] = (rev[i >> 1] >> 1) | (i & 1 ? n >> 1 : 0);
    }
  }
}
using namespace basic;

struct Poly {
  vector<int> a;
  inline int size() {return a.size();}
  inline void resize(int n) {a.resize(n, 0);}
  inline int& operator [] (int x) {return a[x];}

  Poly() {}
  explicit Poly(int n) {a.resize(n);}
  Poly(const vector<int> b) {a = b;}

  inline void NTT(int type) {
    int n = size(); rev_init(n);
    for(int i = 1; i < n; i++) if(i < rev[i]) swap(a[i], a[rev[i]]);
    static int gr[N]; gr[0] = 1;
    for(int d = 1; d < n; d <<= 1) {
      int gw = qpow(type == 1 ? 3 : invg, (mod - 1) / (d << 1));
      for(int i = 1; i < d; i++) {
        gr[i] = 1ll * gr[i - 1] * gw % mod;
      }
      for(int i = 0; i < n; i += d << 1) {
        for(int j = 0; j < d; j++) {
          int x = a[i + j], y = 1ll * gr[j] * a[i + j + d] % mod;
          a[i + j] = add(x, y);
          a[i + j + d] = dec(x, y);
        }
      }
    }
    if(type == -1) {
      for(int i = 0, invn = inv(n); i < n; i++) {
        a[i] = 1ll * invn * a[i] % mod;
      }
    }
  }
  inline friend Poly operator * (Poly A, Poly B) {
    int n = A.size() + B.size() - 1;
    int m = 1; while(m < n) m <<= 1;
    A.resize(m), B.resize(m);
    A.NTT(1), B.NTT(1);
    for(int i = 0; i < m; i++) {
      A[i] = 1ll * A[i] * B[i] % mod;
    }
    A.NTT(-1); A.resize(n);
    return A;
  }

  inline friend Poly operator + (Poly A, Poly B) {
    Poly C(max(A.size(), B.size()));
    for(int i = 0; i < C.size(); i++) {
      if(i < A.size()) ad(C[i], A[i]);
      if(i < B.size()) ad(C[i], B[i]);
    }
    return C;
  }
  inline friend Poly operator - (Poly A, Poly B) {
    Poly C(max(A.size(), B.size()));
    for(int i = 0; i < C.size(); i++) {
      if(i < A.size()) ad(C[i], A[i]);
      if(i < B.size()) de(C[i], B[i]);
    }
    return C;
  }

  inline Poly Inv() {
    Poly g = vector<int>{inv(a[0])};
    while(g.size() < size()) {
      int n = g.size() << 1; 
      int m = n << 1;
      g.resize(m); g.NTT(1);
      Poly h = *this; h.resize(m); h.NTT(1);
      for(int i = 0; i < m; i++) {
        g[i] = 1ll * g[i] * dec(2, 1ll * g[i] * h[i] % mod) % mod;
      }
      g.NTT(-1), g.resize(n);
      // h = g * h; h.resize(n);
      // g = g * (vector<int>{2} - h); g.resize(n);
    }
    g.resize(size());
    return g;
  }

  inline Poly Deriv() {
    if(!size()) return Poly();
    int n = size();
    Poly C(n - 1);
    for(int i = 0; i < n - 1; i++) {
      C[i] = 1ll * (i + 1) * a[i + 1] % mod;
    }
    return C;
  }
  inline Poly Integ() {
    int n = size(); inv_init(n); 
    Poly C(n + 1);
    for(int i = 1; i <= n; i++) {
      C[i] = 1ll * invx[i] * a[i - 1] % mod;
    }
    return C;
  }
  inline Poly Ln() {
    assert(a[0] == 1);
    Poly g = ((*this).Deriv() * (*this).Inv()).Integ();
    g.resize(size());
    return g;
  }

  inline Poly Exp() {
    Poly g = vector<int>{1};
    while(g.size() < size()) {
      int n = g.size() << 1; g.resize(n);
      Poly h = *this; h.resize(n);
      g = g * (vector<int>{1} - g.Ln() + h);
      g.resize(n);
    }
    g.resize(size());
    return g;
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr), cout.tie(nullptr);
  
  int n; cin >> n;
  Poly A(n);
  for(int i = 0; i < n; i++) {
    cin >> A[i];
  }
  A = A.Exp();
  for(int i = 0; i < n; i++) {
    cout << A[i] << " \n"[i == n - 1];
  }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

output:

1 651485948 880456578 579350215 866121094 556313821 206242025 729321342 727650885 28629637 124387075 799846290 262334069 293627 581257465 66131616 111265091 101103433 230183990 101002378 935451184 277980504 251796532 971275611 730166453 886858182 347806129 720413082 110494084 579097933 567943159 881...

result:

wrong answer 2nd numbers differ - expected: '158447743', found: '651485948'

Test #2:

score: 0
Wrong Answer
time: 10ms
memory: 7976kb

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

output:

1 30746689 565934742 751371542 760128029 152968607 743202724 318133535 668399386 640856327 248866828 327963420 7045546 184829317 442793407 784007137 122762725 113053610 893073655 727797404 487641459 698457332 664038879 592265200 104392172 367430184 522280753 377265544 272827479 387348538 834750636 7...

result:

wrong answer 2nd numbers differ - expected: '354399910', found: '30746689'

Test #3:

score: 0
Wrong Answer
time: 42ms
memory: 9428kb

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

output:

1 370142898 907728119 630639832 823194438 341229188 158069940 130433312 644191532 552809741 88288809 438876871 50072802 396509454 276998110 858734676 921564828 347538736 923396442 51616453 740242221 357776828 587083192 521195017 174553976 23676717 347158335 112126460 879719755 259965822 824329263 55...

result:

wrong answer 2nd numbers differ - expected: '147199510', found: '370142898'

Test #4:

score: 0
Wrong Answer
time: 176ms
memory: 15600kb

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

output:

1 700427150 875601715 821788998 812683312 115650768 228334047 637273571 868144005 648030494 419620669 883994413 422329041 280420830 14985517 524569744 7489828 831078459 438893728 310832388 74442276 106407087 87905527 124654525 353122991 493248947 933481667 825755043 886443969 697863922 656251739 341...

result:

wrong answer 2nd numbers differ - expected: '279349013', found: '700427150'

Test #5:

score: 0
Wrong Answer
time: 1695ms
memory: 89052kb

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

output:

1 260403574 732976156 724078143 818932433 226122946 565008428 32554747 614437973 69798906 783618524 66228796 473342878 821615482 506141440 683443288 744421588 306639561 82506326 839469992 367929862 371069424 247427768 554360569 946385504 890509044 715980195 648215937 331613983 737821222 981042435 15...

result:

wrong answer 2nd numbers differ - expected: '204517192', found: '260403574'