QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#303147 | #619. 多项式求逆 | _LAP_ | 0 | 1048ms | 21908kb | C++14 | 3.0kb | 2024-01-11 19:23:50 | 2024-01-11 19:23:52 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> poly;
const int N = 5e6 + 10, MOD = 998244353;
inline int Plus(int a, int b) {return a + b >= MOD ? a + b - MOD : a + b; }
inline int Minus(int a, int b) {return a - b < 0 ? a - b + MOD : a - b; }
inline int ksm(long long a, int b) {
long long r = 1;
for(; b; b >>= 1, a = a * a % MOD)
if(b & 1) r = r * a % MOD;
return r;
}
int rev[N];
inline void NTT(poly &A, int type) {
// type == 1:= DFT
// type == -1:= IDFT
static const int g = 3; // 原根
int n = A.size();
rev[0] = 0;
for(int i = 1; i < n; i ++)
rev[i] = ((rev[i >> 1] >> 1) | (i & 1) * (n >> 1));
for(int i = 0; i < n; i ++)
if(i < rev[i]) swap(A[i], A[rev[i]]);
for(int h = 2; h <= n; h <<= 1) {
long long step = ksm(g, (MOD - 1) / h);
if(type == -1) step = ksm(step, MOD - 2);
for(int i = 0; i < n; i += h)
for(int j = i, mul = 1; j < i + (h >> 1); j ++, mul = mul * step % MOD) {
int u = A[j], v = 1ll * A[j + (h >> 1)] * mul % MOD;
A[j] = Plus(u, v), A[j + (h >> 1)] = Minus(u, v);
}
}
if(type == -1) {
long long mul = ksm(n, MOD - 2);
for(int i = 0; i < n; i ++)
A[i] = A[i] * mul % MOD;
}
}
poly operator + (const poly &lhs, const poly &rhs) {
poly res = lhs; res.resize(max(lhs.size(), rhs.size()), 0);
for(int i = 0; i < rhs.size(); i ++) res[i] = Plus(res[i], rhs[i]);
return res;
}
poly operator - (const poly &lhs, const poly &rhs) {
poly res = lhs; res.resize(max(lhs.size(), rhs.size()), 0);
for(int i = 0; i < rhs.size(); i ++) res[i] = Minus(res[i], rhs[i]);
return res;
}
poly operator * (const int lhs, const poly &rhs) {
poly res = rhs;
for(int i = 0; i < rhs.size(); i ++)
res[i] = 1ll * res[i] * lhs % MOD;
return res;
}
poly operator * (const poly &lhs, const int rhs) {
poly res = lhs;
for(int i = 0; i < lhs.size(); i ++)
res[i] = 1ll * res[i] * rhs % MOD;
return res;
}
poly operator * (poly A, poly B) {
int h = 1;
while(h <= A.size() + B.size()) h <<= 1;
A.resize(h, 0), B.resize(h, 0);
NTT(A, 1), NTT(B, 1);
for(int i = 0; i < h; i ++) A[i] = 1ll * A[i] * B[i] % MOD;
NTT(A, -1); return A;
}
inline poly inv(poly A, int n) {
int h = 1; while(h <= n) h <<= 1; A.resize(h, 0);
if(A.empty()) return poly();
poly res(1, ksm(A[0], MOD - 2));
for(int i = 2; i <= h; i <<= 1) {
poly t = res; t.resize(i >> 1, 0), t.resize(i * 2, 0);
t = t * t; t.resize(i * 2, 0); t = t * A; t.resize(i * 2, 0);
res = 2 * res - t;
}
res.resize(n + 1); return res;
}
int main() {
ios::sync_with_stdio(false), cin.tie(0);
int n; cin >> n; poly f(n);
for(int i = 0; i < n; i ++)
cin >> f[i];
poly g = inv(f, n);
for(int i = 0; i < n; i ++)
cout << g[i] << " \n"[i == n - 1];
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3528kb
input:
100 321704272 732147873 495950455 607498198 139258053 834073875 837326587 9642661 903437916 207412353 359180940 720085797 719290810 723076036 984279000 503225771 350175866 162829281 512559053 225874248 808881115 775602122 556705696 16814894 894905093 985867138 253650922 979472539 59109787 205995179 ...
output:
890391751 343178682 709950581 248573740 155003792 121063153 971739900 888240696 926095011 284929631 882976199 542279543 131651533 977789433 167757891 918195456 560856885 755976112 34039567 302980664 467112024 458903443 580863066 232408790 712746461 420666055 220260689 852614570 788749038 702552591 7...
result:
wrong answer 65th numbers differ - expected: '548459973', found: '834574400'
Test #2:
score: 0
Wrong Answer
time: 44ms
memory: 6212kb
input:
5000 895174753 48640370 621768187 544696442 266653647 800854366 993400253 180889611 259138834 922465819 237366500 134204023 882884556 962623362 906378209 783980105 385064692 526608265 306798389 492937123 600567928 363960265 499995507 901802313 322681104 915889147 191761221 168327309 250045818 379937...
output:
682334353 436976416 775272797 222487943 387482624 578444714 913440174 91807434 793656036 840531807 501588255 564297941 790458031 279039057 788782851 217732094 55414463 556674881 556372136 207469922 22960536 808480214 237927525 393440457 740345941 957397909 844601165 902029038 247139335 2283882 54979...
result:
wrong answer 4097th numbers differ - expected: '597163324', found: '699871579'
Test #3:
score: 0
Wrong Answer
time: 215ms
memory: 8748kb
input:
30000 433849057 26933151 94119735 348782922 994201565 286266085 253836562 391505281 561460922 76317536 151770395 626212470 835627785 278418333 560388198 586773695 43090005 450934659 716357773 746228248 47588293 745422420 131896260 923566007 275614901 981279191 966289868 111837778 850083076 346727100...
output:
357845866 278279787 282399673 535141130 667648994 63737517 190046919 326102148 662204122 372177710 538590284 867601509 319250982 253971547 418533239 965211653 475013466 104848869 679833017 632683281 154028567 253417158 839386097 24193741 852729812 320234422 132258378 976799786 627417267 278166273 69...
result:
wrong answer 16385th numbers differ - expected: '22977263', found: '694479310'
Test #4:
score: 0
Wrong Answer
time: 1048ms
memory: 21908kb
input:
100000 299085935 896290047 664961463 798136437 284888760 805376081 754380153 982440654 523416648 618138054 639229548 946675552 216492659 801950754 591895463 409803161 734598818 262678735 505505080 132772037 241184558 549895828 778274609 60046418 766879997 555641192 925835147 535599922 727361907 2850...
output:
152663231 835829855 733898831 594740161 134406704 39940730 895052135 225966750 351630054 544215344 168586029 481785131 709831593 661056822 235154057 493601823 22230265 160367609 731879071 652142676 233990007 379664191 476172493 836696871 945774957 283346933 426801303 581100604 610982192 940304348 20...
result:
wrong answer 65537th numbers differ - expected: '445181754', found: '971622364'
Test #5:
score: 0
Time Limit Exceeded
input:
1000000 737044976 941398691 939287417 273413335 175365852 377721127 3862986 176449650 791765055 129385383 433663518 447033570 279210233 157228851 130509370 963480863 130226624 349605390 600289609 890766355 577960206 537162643 776878360 951933771 688851169 624945579 212339598 106077966 426859950 6284...