QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#6831 | #621. 多项式指数函数 | Lenstar | 80 | 470ms | 112716kb | C++11 | 4.7kb | 2021-03-12 19:17:51 | 2021-12-19 09:42:18 |
Judging History
answer
#include <bits/stdc++.h>
namespace io
{
const int bufsize = (1 << 20) + 10;
char fin[bufsize], *p1 = fin, *p2 = fin;
inline char nc()
{
return p1 == p2 && (p2 = (p1 = fin) + fread(fin, 1, bufsize, stdin), p1 == p2) ? EOF : *p1++;
}
template<typename T = int> inline T read()
{
T x = 0; int f = 0; char ch = nc();
while (!isdigit(ch)) f |= ch == '-', ch = nc();
while ( isdigit(ch)) x = x * 10 + ch - '0', ch = nc();
return x;
}
char fout[bufsize], *q1 = fout, *q2 = fout + bufsize;
inline void pc(char c)
{
if (q1 == q2) q2 = (q1 = fout) + fwrite(fout, 1, bufsize, stdout);
*q1++ = c;
}
inline void pc(char *s)
{
while (*s) pc(*s++);
}
inline void flush()
{
fwrite(fout, 1, q1 - fout, stdout), fflush(stdout);
}
template<typename T> inline void put(T x)
{
if (x > 9) put(x / 10); pc(x % 10 + '0');
}
template<typename T> inline void write(T x, char ch = ' ')
{
put(x), pc(ch);
}
}
const int N = 3e6 + 10, Mod = 998244353;
inline int chk(int a) {return a >= Mod ? a - Mod : a;}
inline int Pow(int a, int b, int mod = Mod)
{
int res = 1;
for (; b; b >>= 1, a = 1LL * a * a % mod)
if (b & 1) res = 1LL * res * a % mod;
return res;
}
namespace poly
{
const int len = 21, G = 3, InvG = (Mod + 1) / G;
int GPow[2][len + 1][1 << len];
inline void init()
{
for (int p = 1; p <= len; ++p)
{
int buf0 = Pow(G, (Mod + 1) / (1 << p));
int buf1 = Pow(InvG, (Mod + 1) / (1 << p));
GPow[0][p][0] = GPow[1][p][0] = 1;
for (int i = 1; i < (1 << p); ++i)
{
GPow[0][p][i] = 1LL * GPow[0][p][i - 1] * buf0 % Mod;
GPow[1][p][i] = 1LL * GPow[1][p][i - 1] * buf1 % Mod;
}
}
}
int rev[N];
inline void ntt(int *a, int len, int f = 0)
{
int k = 0; while ((1 << k) < len) k++;
for (int i = 0; i < len; ++i)
{
rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << k - 1);
if (i < rev[i]) std::swap(a[i], a[rev[i]]);
}
for (int l = 2, cnt = 1; l <= len; l <<= 1, ++cnt)
for (int i = 0, m = l >> 1; i < len; i += l)
for (int j = 0, *buf = GPow[f][cnt]; j < m; ++j, ++buf)
{
int p = a[i + j], q = 1LL * a[i + j + m] * *buf % Mod;
a[i + j] = chk(p + q), a[i + j + m] = chk(p - q + Mod);
}
if (f)
{
int inv = Pow(len, Mod - 2);
for (int i = 0; i < len; ++i) a[i] = 1LL * a[i] * inv % Mod;
}
}
inline void inv(int n, int *a, int *b)
{
if (n == 1)
{
b[0] = Pow(a[0], Mod - 2);
return;
}
inv(n + 1 >> 1, a, b);
static int c[N]; int len = 1;
while (len < 2 * n) len <<= 1;
for (int i = 0; i < n ; ++i) c[i] = a[i];
for (int i = n; i < len; ++i) c[i] = b[i] = 0;
ntt(b, len), ntt(c, len);
for (int i = 0; i < len; ++i) b[i] = 1LL * b[i] * chk(Mod + 2 - 1LL * b[i] * c[i] % Mod) % Mod;
ntt(b, len, 1);
for (int i = n; i < len; ++i) b[i] = 0;
}
inline void ln(int n, int *a, int *b)
{
static int c[N]; int len = 1;
for (int i = 1; i < n; ++i) c[i - 1] = 1LL * i * a[i] % Mod; c[n - 1] = 0;
inv(n, a, b); while (len < 2 * n) len <<= 1;
for (int i = n; i < len; ++i) c[i] = 0;
ntt(b, len), ntt(c, len);
for (int i = 0; i < len; ++i) b[i] = 1LL * b[i] * c[i] % Mod;
ntt(b, len, 1);
for (int i = n - 1; i >= 0; --i) b[i] = 1LL * b[i - 1] * Pow(i, Mod - 2) % Mod;
b[0] = 0;
}
inline void exp(int n, int *a, int *b)
{
if (n == 1) return void(b[0] = 1);
static int c[N];
exp(n + 1 >> 1, a, b), ln(n, b, c);
int len = 1; while (len < n * 2) len <<= 1;
for (int i = 0; i < n ; ++i) c[i] = chk(a[i] - c[i] + Mod); c[0] = chk(c[0] + 1);
for (int i = n; i < len; ++i) c[i] = b[i] = 0;
ntt(b, len), ntt(c, len);
for (int i = 0; i < len; ++i) b[i] = 1LL * b[i] * c[i] % Mod;
ntt(b, len, 1);
for (int i = n; i < len; ++i) b[i] = 0;
}
}
int a[N], b[N], c[N];
int main()
{
int n = io::read(); poly::init();
for (int i = 0; i < n; ++i) a[i] = io::read();
poly::exp(n, a, b);
for (int i = 0; i < n; ++i) io::write(b[i]);
return io::flush(), 0;
}
詳細信息
Test #1:
score: 20
Accepted
time: 23ms
memory: 107856kb
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:
1 158447743 989903074 918187254 200068193 455062373 11196740 759336019 312075964 992242039 123230223 144998958 189062409 420150911 170942299 432890803 760087114 639614944 787205333 63667632 243571846 141993017 450288335 173318832 743144111 879389773 95666186 453410000 569486107 512729334 226210545 583843354 770244187 506859030 960348003 591955543 326668069 283535201 545276198 756666623 637645543 988390418 279027521 811851748 195335516 883324003 39642660 43553758 860245759 187849991 369088108 615...
result:
ok 100 numbers
Test #2:
score: 20
Accepted
time: 36ms
memory: 107556kb
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:
1 354399910 51676417 184411965 928033808 589971658 936383703 745898312 943454394 65252947 270867254 772620225 995104944 58521883 96491645 326592384 283913887 140742590 960115688 684602174 623426872 184484323 952879775 315489867 167038509 580362327 164714100 833258994 345402076 261957154 469710461 98909201 912220730 797482583 110446889 461158009 511291755 194079400 849976694 733749911 326177532 376934943 70169116 601713259 875738061 613122597 177648796 980516154 19290301 629815611 210848998 10036...
result:
ok 5000 numbers
Test #3:
score: 20
Accepted
time: 132ms
memory: 108976kb
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:
1 147199510 30930552 734023222 564008583 299902819 450980389 806779390 654937901 981162061 206882721 35851319 707998765 357594654 305814262 734562024 591099032 543969413 539432668 154163976 451201740 856569012 898961429 732819402 243444529 673245321 601964526 206333661 876679409 438174247 903706710 721924549 366525586 182013075 390789902 864037091 410595937 353024238 970691911 570639496 66536517 107591114 700244315 429693759 419045658 4401063 873683305 106667518 211342016 289811703 929820725 107...
result:
ok 30000 numbers
Test #4:
score: 20
Accepted
time: 470ms
memory: 112716kb
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:
1 279349013 426120005 205100346 421201310 474118168 879116053 749708347 23319122 872190753 903275287 797670709 327019687 707029564 46014243 838268797 28223150 48499086 927009654 52188573 200586020 4624185 827007182 201682326 552029133 820855946 97607062 601649418 37529652 24405665 116064030 620516317 954331876 448141495 376194952 97146001 288311515 992837065 548519462 188045151 853500007 152581028 435901883 135969796 482104252 307859632 112811323 903041365 525769409 402229514 778972652 345568114...
result:
ok 100000 numbers
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...