QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#86233 | #5360. Wechat | xiaoyaowudi | 0 | 2ms | 14732kb | C++14 | 5.0kb | 2023-03-09 16:00:30 | 2023-03-09 16:00:33 |
Judging History
answer
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
using ll=long long;
namespace polynomial
{
constexpr int P(998244353),N(200010),PR(3),APR((P+1)/PR);
int ws[2][N<<2],fac[N<<2],ifac[N<<2],fn,fb,lgg[N<<2],_inv[N<<2],rev[N<<2];
int fast_pow(int a,int b){int ans(1),off(a);while(b){if(b&1) ans=1ll*ans*off%P;off=1ll*off*off%P;b>>=1;}return ans;}
void init_poly_weights(int len)
{
fn=1,fb=0;while(fn<(len<<1)) fn<<=1,++fb;
_inv[1]=1;for(int i(2);i<=fn;++i) _inv[i]=1ll*(P-P/i)*_inv[P%i]%P;
ifac[0]=fac[0]=1;for(int i(1);i<=fn;++i) fac[i]=1ll*i*fac[i-1]%P,ifac[i]=1ll*ifac[i-1]*_inv[i]%P;
for(int i(0);i<fn;++i) rev[i]=(rev[i>>1]>>1)|((i&1)<<(fb-1));
for(int i(2);i<=fn;++i) lgg[i]=lgg[(i+1)>>1]+1;
for(int mid((fn>>1)),j0(fast_pow(PR,(P-1)/(mid<<1))),j1(fast_pow(APR,(P-1)/(mid<<1)));mid>=1;mid>>=1,j0=1ll*j0*j0%P,j1=1ll*j1*j1%P)
for(int i(0),w0(1),w1(1);i<mid;++i,w0=1ll*w0*j0%P,w1=1ll*w1*j1%P) ws[0][i+mid]=w0,ws[1][i+mid]=w1;
}
using poly=std::vector<int>;
int redu(int k){return k>=P?k-P:k;}
poly operator+(const poly &a,const poly &b)
{
poly ret(b);if(ret.size()<a.size()) ret.resize(a.size());
for(int i(0);i<a.size();++i) ret[i]=redu(ret[i]+a[i]);
return ret;
}
unsigned long long tt[N<<2];
void NTT(poly &p,int V)
{
int bts(lgg[p.size()]);if(p.size()!=(1<<bts)) p.resize((1<<bts));
int* w(ws[(V==1)?0:1]),len(1<<bts);for(int i(0);i<len;++i) tt[i]=p[rev[i]>>(fb-bts)];
unsigned long long t1,t2;
for(int l(2);l<=len;l<<=1)
for(int j(0),mid=(l>>1);j<len;j+=l)
for(int i(0);i<mid;++i) t1=tt[j+i],t2=tt[j+i+mid]*w[mid+i]%P,tt[j+i]=t1+t2,tt[j+i+mid]=P+t1-t2;
if(V==1) for(int i(0);i<len;++i) p[i]=tt[i]%P;
else for(int i(0),j(_inv[len]);i<len;++i) p[i]=tt[i]%P*j%P;
}
poly operator*(const poly &a,const poly &b)
{
static poly p1,p2;poly ret;
p1=a,p2=b;int len(a.size()+b.size()-1),ff(1<<lgg[len]);
p1.resize(ff),p2.resize(ff),ret.resize(ff);
NTT(p1,1);NTT(p2,1);
for(int i(0);i<ff;++i) ret[i]=1ll*p1[i]*p2[i]%P;
NTT(ret,-1);ret.resize(len);return ret;
}
void print_poly(const poly &a){for(int v:a) printf("%d ",v);printf("\n");}
poly poly_inv(const poly &a)
{
int l(a.size());if(l==1){poly ret(1);ret[0]=fast_pow(a[0],P-2);return ret;}
poly g0(a);g0.resize((l+1)>>1);g0=poly_inv(g0);
static poly p1;p1=a;int ff(2<<lgg[l]);poly ret(ff);g0.resize(ff);p1.resize(ff);
NTT(p1,1);NTT(g0,1);for(int i(0);i<ff;++i) ret[i]=1ll*g0[i]*(2-1ll*g0[i]*p1[i]%P+P)%P;
NTT(ret,-1);ret.resize(l);return ret;
}
poly poly_ln(const poly &a)
{
int l(a.size());static poly p1;
p1.resize(l-1);for(int i(1);i<l;++i) p1[i-1]=1ll*i*a[i]%P;
p1=p1*poly_inv(a);p1.resize(l-1);poly ret(l);
for(int i(1);i<l;++i) ret[i]=1ll*_inv[i]*p1[i-1]%P;ret[0]=0;
return ret;
}
poly poly_exp(const poly &a)
{
int l(a.size());if(l==1){poly ret(1);ret[0]=1;return ret;}
poly g0(a);g0.resize((l+1)>>1);g0=poly_exp(g0);static poly g1,g2;g1=g0;g1.resize(l);g1=poly_ln(g1);g2=a;
int ff(2<<lgg[l]);g0.resize(ff);g1.resize(ff);poly ret(ff);g2.resize(ff);
NTT(g0,1);NTT(g1,1);NTT(g2,1);
for(int i(0);i<ff;++i) ret[i]=1ll*g0[i]*(1-g1[i]+g2[i]+P)%P;
NTT(ret,-1);ret.resize(l);return ret;
}
std::pair<int,int> cf[N];// u/(1+dx)
std::pair<poly,poly> calc(int l,int r)
{
if(l==r)
{
auto [u,d]=cf[l];
return {{u},{1,d}};
}
int mid((l+r)>>1);
auto [ls,lt]=calc(l,mid);
auto [rs,rt]=calc(mid+1,r);
int T(1<<lgg[r-l+2]);ls.resize(T);lt.resize(T);rs.resize(T);rt.resize(T);
poly s(T),t(T);
NTT(ls,1);NTT(lt,1);NTT(rs,1);NTT(rt,1);
for(int i(0);i<T;++i) s[i]=(1ll*ls[i]*rt[i]+1ll*rs[i]*lt[i])%P,t[i]=1ll*lt[i]*rt[i]%P;
NTT(s,-1);NTT(t,-1);s.resize(r-l+1);t.resize(r-l+2);
return {s,t};
}
poly solve_fs(const std::vector<std::pair<int,int>> &a,int m)
{
int n(a.size());
std::copy(a.begin(),a.end(),cf+1);
auto [s,t]=calc(1,n);
t.resize(m+1);
t=poly_inv(t);
s=s*t;
s.resize(m+1);
return s;
}
const poly unit_poly={1};
}
using polynomial::poly;
using polynomial::operator*;
using polynomial::operator+;
using polynomial::init_poly_weights;
using polynomial::unit_poly;
using polynomial::print_poly;
using polynomial::poly_inv;
using polynomial::poly_exp;
using polynomial::poly_ln;
using polynomial::solve_fs;
constexpr int N(100010),p(998244353);
int fp(int a,int b){int ans(1),off(a);while(b){if(b&1) ans=1ll*ans*off%p;off=1ll*off*off%p;b>>=1;}return ans;}
int main()
{
static int inv[N],fac[N],ifac[N];inv[1]=1;
for(int i(2);i<N;++i) inv[i]=1ll*inv[p%i]*(p-p/i)%p;ifac[0]=fac[0]=1;
for(int i(1);i<N;++i) fac[i]=1ll*fac[i-1]*i%p,ifac[i]=1ll*ifac[i-1]*inv[i]%p;
int n;std::cin>>n;init_poly_weights(n+1);
poly p1(n+1),p2(n+1);
for(int i(0);i<=n;++i)
{
p2[i]=(i&1)?p-ifac[i]:ifac[i];
p1[i]=1ll*ifac[n]*fp(i,n)%p*ifac[i]%p;
}
poly r(p1*p2);
poly k(n);
for(int i(0);i<n;++i) k[i]=1ll*fac[n-i]*r[n-i]%p*fac[i]%p;
std::reverse(k.begin(),k.end());
k=k*p2;
k.resize(n);std::reverse(k.begin(),k.end());
for(int i(0);i<n;++i) std::cout<<1ll*k[i]*fac[i]%p<<" ";
std::cout<<std::endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 2ms
memory: 14732kb
input:
10
output:
370705776 185074360 18838121 753991394 504192832 625888564 570490372 334880 453824 36288
result:
wrong answer 1st lines differ - expected: '370705776 185074360 753392795 ...5 753392795 185074360 370705776', found: '370705776 185074360 18838121 7... 570490372 334880 453824 36288 '
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Skipped
Dependency #1:
0%
Subtask #4:
score: 0
Skipped
Dependency #1:
0%
Subtask #5:
score: 0
Skipped
Dependency #1:
0%