QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#131432 | #621. 多项式指数函数 | wunuowang | 100 ✓ | 2587ms | 136068kb | C++14 | 6.1kb | 2023-07-27 07:44:02 | 2023-07-27 07:44:04 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pd push_back
#define all(x) x.begin(),x.end()
//==============================================================
ll QP(ll x,ll y,ll mod){ll ans=1;for(;y;y>>=1,x=x*x%mod)if(y&1)ans=ans*x%mod;return ans;}
ll inv(ll x,ll mod){return QP(x,mod-2,mod);}
//==============================================================
namespace IO{
int readInt(){
int x=0,y=0;char c=0;
while(!isdigit(c))y|=c=='-',c=getchar();
while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
return !y?x:-x;
}
}
//===============================================================
const int N=5e6+10;
const int g=3,mod=998244353,G=3;
//int w[40]={0,998244352,911660635,372528824,929031873,452798380,922799308,781712469,476477967,
// 166035806,258648936,584193783,63912897,350007156,666702199,968855178,629671588,24514907,
// 996173970,363395222,565042129,733596141},
// w0[40]={0,998244352,86583718,509520358,337190230,87557064,609441965,135236158,304459705,685443576,
// 381598368,335559352,129292727,358024708,814576206,708402881,283043518,3707709,121392023,
// 704923114,950391366,428961804};
//ll g1=QP(opt==1?g:gi,(mod-1)/(i<<1),mod);
//void init1(){
// for(int i=1,p=1;i<=2e6;i<<=1,p++)w[p]=QP(g,(mod-1)/(i<<1),mod);
// for(int i=1,p=1;i<=2e6;i<<=1,p++)w0[p]=QP(gi,(mod-1)/(i<<1),mod);
//}
//vector<int> rev;
int gi[N];
//void Resize(int n){rev.resize(n<<1);}
void init1(int n){
for(int i=2;i<=n;i<<=1){
int gn=QP(G,(mod-1)/i,mod);
gi[i>>1]=1;
for(int j=(i>>1)+1;j<i;j++)
gi[j]=1ll*gi[j-1]*gn%mod;
}
}
namespace Math{
//int fac[N],nfac[N];
int Iv[N];
// void initfac(){
// fac[0]=1;for(int i=1;i<=N-10;i++)fac[i]=1ll*fac[i-1]*i%mod;
// nfac[N-10]=inv(fac[N-10],mod);for(int i=N-11;~i;i--)nfac[i]=1ll*nfac[i+1]*(i+1)%mod;
// }int C(int x,int y){return x<0||y<0||x<y?0:1ll*fac[x]*nfac[y]%mod*nfac[x-y]%mod;}
void initinv(){
Iv[1]=1;
for(int i=2;i<=N-10;i++)
Iv[i]=1ll*(-1ll*Iv[mod%i]*(mod/i)%mod+mod)%mod;
}
}
#define add(x) (x+(x<0?mod:0)-(x>=mod?mod:0))
struct Poly{
vector<int> v;
inline void read(int n){v.resize(n+1);for(int i=0;i<=n;i++){v[i]=IO::readInt();if(v[i]>=mod)v[i]-=mod;};}
inline void write(int n){for(int i=0;i<=n;i++)printf("%d ",v[i]);puts("");return;}
inline void debug(){for(auto y:v)printf("%d ",y);puts("");return;}
//=========================================================================
inline void clear(int n){while(v.size()>n+1)v.pop_back();}
//=========================================================================
inline int operator [](const int &i)const{
if(v.size()<=i)return 0;
else return v[i];
}inline int& operator [](const int &i){
if(v.size()<=i)v.resize(i+1);
return v[i];
}
//==========================================================================
inline int init2(int n,int m){
int lim=0;
while((1<<lim)<=n+m)lim++;
// for(int i=0;i<(1<<lim);i++)rev[i]=(rev[i>>1]>>1)|((i&1)?(1<<lim-1):0);
return lim;
}
//==========================================================================
inline void NTT(Poly &f,const int &n){
for(int i=n>>1;i;i>>=1)
for(int j=0;j<n;j+=(i<<1))
for(int k=0,x,y;k<i;k++)
x=f[j|k],y=f[i|j|k],
f[j|k]=x+y-(x+y>=mod?mod:0),
f[i|j|k]=1ll*gi[i|k]*(x-y+(x-y<0?mod:0))%mod;
}
inline void INTT(Poly &f,const int &n){
for(int i=1;i<n;i<<=1)
for(int j=0;j<n;j+=(i<<1))
for(int k=0,x,y;k<i;k++)
x=f[j|k],y=1ll*gi[i|k]*f[i|j|k]%mod,
f[j|k]=x+y-(x+y>=mod?mod:0),f[i|j|k]=(x-y+(x-y<0?mod:0));
int Inv=inv(n,mod);
reverse(f.v.begin()+1,f.v.begin()+n);
for(int i=0;i<n;i++)f[i]=1ll*f[i]*Inv%mod;
}inline Poly convolution(Poly A,Poly B){
int lim=init2(A.v.size()-1,B.v.size()-1);
// A.debug();B.debug();
NTT(A,1<<lim);NTT(B,1<<lim);
// A.debug();B.debug();
for(int i=0;i<(1<<lim);i++)A[i]=1ll*A[i]*B[i]%mod;
INTT(A,(1<<lim));
// for(auto y:A.v)printf("%d ",y);puts("");
return A;
}
inline void Ginv(Poly &S,int n){
if(n==1)return S[0]=inv(v[0],mod),void();
Ginv(S,n+1>>1);int lim=1,len=0;
for(;lim<(n<<1);lim<<=1,len++);
// lim=1<<len;
//for(int i=1;i<lim;i++)
// rev[i]=(rev[i>>1]>>1)|((i&1)?(1<<len-1):0);
Poly A;
for(int i=n;~i;i--)A[i]=(*this)[i];
NTT(A,lim);NTT(S,lim);
for(int i=0;i<lim;i++)
S[i]=1ll*(2ll-1ll*A[i]*S[i]%mod+mod)*S[i]%mod;
INTT(S,lim);
S.clear(n-1);
}inline Poly Inv(){
Poly ans;
Ginv(ans,v.size());
ans.clear(v.size()-1);
return ans;
}inline Poly DifCalc(){
Poly S;
for(int i=0;i<v.size()-1;i++)
S[i]=1ll*v[i+1]*(i+1)%mod;
return S;
}inline Poly IntCalc(){
Poly S;S[0]=0;
for(int i=0;i<v.size();i++)
S[i+1]=1ll*v[i]*Math::Iv[i+1]%mod;
return S;
}inline Poly ln(){
assert(v[0]==1);
Poly S=((*this).DifCalc()*(*this).Inv()).IntCalc();
S.clear(v.size()-1);
return S;
}
inline int upp(int x){return 1<<(__lg(x-1)+1);}
inline void Gexp(Poly &S,int n){
if(n==1)return S[0]=1,void();
Gexp(S,n+1>>1);
Poly A=S.ln();
for(int i=0;i<n;i++)A[i]=0ll+(*this)[i]-A[i]+((*this)[i]-A[i]<0?mod:0);A[0]=(A[0]+1-(A[0]+1>=mod?mod:0));
S=S*A;S.clear(n-1);
// S.debug();
}
inline Poly exp(){
Poly ans;//int lim=1;
//for(;lim<=v.size();lim<<=1);
Gexp(ans,v.size()<<1);
ans.clear(v.size()-1);
return ans;
}inline Poly QuickPow(int k){
assert((*this)[0]==1);
Poly A=(*this).ln();
for(int i=0;i<A.v.size();i++)A[i]=1ll*A[i]*k%mod;
return A.exp();
}
//==========================================================================
inline Poly operator * (const Poly &y){
Poly ans=convolution((*this),y);
ans.clear(((*this).v.size()-1)+(y.v.size()-1));
return ans;
}inline Poly operator ^ (const int &y){return QuickPow(y);}
};int n,m;Poly x;
int k=0;
char c[N];
int main(){
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
//init1();
Math::initinv();
init1(N-1);
// for(int i=0;i<=30;i++)cout<<w0[i]<<' ';
n=IO::readInt();n--;
// scanf("%s",c+1);int l=strlen(c+1);
x.read(n);
//for(int i=1;i<=l;i++)k=(1ll*k*10+ll(c[i]-'0'))%mod;
x.exp().write(n);
return 0;
}
详细
Test #1:
score: 20
Accepted
time: 41ms
memory: 40652kb
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 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 5...
result:
ok 100 numbers
Test #2:
score: 20
Accepted
time: 56ms
memory: 42780kb
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 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 98...
result:
ok 5000 numbers
Test #3:
score: 20
Accepted
time: 97ms
memory: 45076kb
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 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 ...
result:
ok 30000 numbers
Test #4:
score: 20
Accepted
time: 320ms
memory: 52716kb
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 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 62051631...
result:
ok 100000 numbers
Test #5:
score: 20
Accepted
time: 2587ms
memory: 136068kb
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 204517192 619471860 517479130 453571099 756084155 250936574 733632267 123356262 736823877 36879005 134860159 91607107 898896915 410588432 269428255 936285724 807500080 148699607 694600424 104902381 245153045 814276600 610840817 459421157 797608659 275590448 967892574 251820609 688675003 675994534 ...
result:
ok 1000000 numbers