QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#6832 | #621. 多项式指数函数 | zombie462 | 0 | 0ms | 0kb | C++ | 3.5kb | 2021-03-12 19:18:23 | 2021-12-19 09:42:25 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N=1<<22;
int fac[N],inv[N],ifac[N],rev[N],omg[2][N];
int read(){
int x=0,f=1;
char ch=getchar();
while (ch<'0' || ch>'9'){
if (ch=='-') f=-f;
ch=getchar();
}
while (ch>='0' && ch<='9'){
x=x*10+ch-48;
ch=getchar();
}
return x*f;
}
const int mod=998244353;
int mul(int x,int y){
return 1LL*x*y%mod;
}
int sub(int x,int y){
return x-y<0?x-y+mod:x-y;
}
int add(int x,int y){
return x+y>=mod?x+y-mod:x+y;
}
int getinv(int x){
return x<=1?1:mul(mod-mod/x,getinv(mod%x));
}
int fpow(int x,int y){
int res=1;
while (y){
if (y&1) res=mul(res,x);
x=mul(x,x);y>>=1;
}
return res;
}
void NTT(vector <int> &a,int op){
int lim=a.size(),len=log2(lim);
for (int i=0;i<=lim-1;++i){
int r=rev[i]>>(18-len);
if (i<r) swap(a[i],a[r]);
}
for (int i=1;i<=lim-1;i<<=1){
for (int j=0;j<=lim-1;j+=i<<1){
for (int k=0;k<=i-1;++k){
int tmp=mul(omg[op][N/(i<<1)*k],a[i+j+k]);
a[i+j+k]=sub(a[j+k],tmp);a[j+k]=add(a[j+k],tmp);
}
}
}
if (op){
int invn=getinv(lim);
for (int i=0;i<=lim-1;++i) a[i]=mul(a[i],invn);
}
}
vector <int> getinv(vector <int> a){
int n=a.size();vector <int> b={getinv(a[0])};
a.resize(1<<(int)ceil(log2(n)));
for (int lim=2;lim<=2*n-1;lim<<=1){
vector <int> c(a.begin(),a.begin()+lim);
c.resize(lim<<1);NTT(c,0);
b.resize(lim<<1);NTT(b,0);
for (int i=0;i<=(lim<<1)-1;++i) b[i]=mul(sub(2,mul(c[i],b[i])),b[i]);
NTT(b,1);b.resize(lim);
}
b.resize(n);return b;
}
vector <int> log(vector <int> a){
int n=a.size();vector <int> b=getinv(a);
for (int i=0;i<=n-2;++i) a[i]=mul(a[i+1],i+1);
a.resize(n-1);
int lim=1<<(int)ceil(log2(2*n-2));
a.resize(lim);NTT(a,0);
b.resize(lim);NTT(b,0);
for (int i=0;i<=lim-1;++i) a[i]=mul(a[i],b[i]);
NTT(a,1);a.resize(n);
for (int i=n-1;i>=1;--i) a[i]=mul(a[i-1],inv[i]);
a[0]=0;return a;
}
vector <int> exp(vector <int> a){
int n=a.size();vector <int> b={1};
a.resize(1<<(int)ceil(log2(n)));
for (int lim=2;lim<=2*n-1;lim<<=1){
b.resize(lim);vector <int> c=log(b);
c[0]=sub(1+a[0],c[0]);
for (int i=1;i<=lim-1;++i) c[i]=sub(a[i],c[i]);
c.resize(lim<<1);NTT(c,0);
b.resize(lim<<1);NTT(b,0);
for (int i=0;i<=(lim<<1)-1;++i) b[i]=mul(c[i],b[i]);
NTT(b,1);b.resize(lim);
}
b.resize(n);
return b;
}
vector <int> operator * (vector <int> a,vector <int> b){
int n=a.size()+b.size()-1,lim=1<<(int)ceil(log2(n));
a.resize(lim);NTT(a,0);
b.resize(lim);NTT(b,0);
for (int i=0;i<=lim-1;++i) a[i]=mul(a[i],b[i]);
NTT(a,1);a.resize(n);
return a;
}
vector <int> operator * (vector <int> a,int b){
int n=a.size();
for (int i=0;i<n;++i) a[i]=mul(a[i],b);
return a;
}
vector <int> operator ^ (vector <int> a,int b){
return exp(log(a)*b);
}
vector <int> sqrt(vector <int> a,int b=2){
return a^getinv(b);
}
void init(){
omg[0][0]=1;omg[0][1]=fpow(3,(mod-1)/N);for (int i=2;i<=N-1;++i) omg[0][i]=mul(omg[0][i-1],omg[0][1]);
omg[1][0]=1;omg[1][1]=getinv(omg[0][1]);for (int i=2;i<=N-1;++i) omg[1][i]=mul(omg[1][i-1],omg[1][1]);
rev[0]=0;rev[1]=1<<21;for (int i=2;i<=N-1;++i) rev[i]=rev[i>>1]>>1|(i&1)<<21;
fac[0]=fac[1]=1;for (int i=2;i<=N-1;++i) fac[i]=mul(fac[i-1],i);
inv[0]=inv[1]=1;for (int i=2;i<=N-1;++i) inv[i]=mul(mod-mod/i,inv[mod%i]);
ifac[0]=ifac[1]=1;for (int i=2;i<=N-1;++i) ifac[i]=mul(ifac[i-1],inv[i]);
}
signed main(){
vector <int> a;init();
int n=read()-1;a.resize(n+1);
for (int i=0;i<=n;++i) a[i]=read();
a=exp(a);
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
Runtime Error
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:
result:
Test #3:
score: 0
Runtime Error
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:
result:
Test #4:
score: 0
Runtime Error
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:
result:
Test #5:
score: 0
Runtime Error
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...