QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#110279 | #4472. 珍珠 | xiaoyaowudi | 100 ✓ | 44ms | 16624kb | C++17 | 5.6kb | 2023-06-01 13:11:42 | 2023-06-01 13:11:45 |
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],fn,fb,inv[N<<2],rev[N<<2],fac[N<<2],ifac[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;
fac[0]=ifac[0]=1;for(int i(1);i<=fn;++i) fac[i]=1ll*fac[i-1]*i%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 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];
int ntt_bits(int k){return std::__lg(std::max(k-1,1))+1;}
void NTT(poly &p,int V)
{
int bts(ntt_bits(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<<ntt_bits(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;
}
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);int t(g0.size()),tb(ntt_bits(t<<1));
poly f(a),g(g0);f.resize(1<<tb);g0.resize(1<<tb);NTT(f,1);NTT(g0,1);
for(int i(0);i<(1<<tb);++i) f[i]=(1+1ll*(P-f[i])*g0[i])%P;
NTT(f,-1);f.erase(f.begin(),f.begin()+t);f.resize(1<<tb);
NTT(f,1);for(int i(0);i<(1<<tb);++i) f[i]=1ll*f[i]*g0[i]%P;
NTT(f,-1);g.resize(l);std::copy(f.begin(),f.begin()+l-t,g.begin()+t);return g;
}
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<<ntt_bits(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;
}
poly poly_pow(const poly &a,int k)
{
int l(a.size());
if(!k){poly r(l);r[0]=1;return r;}
int i(0);while(i<l && !a[i]) ++i;
if(1ll*i*k>=l) return poly(l);
poly f(a.begin()+i,a.begin()+i+l-i*k);
int t(f[0]),_t(fast_pow(t,P-2));
for(int &v:f) v=1ll*_t*v%P;t=fast_pow(t,k);
f=poly_ln(f);
for(int &v:f) v=1ll*v*k%P;
f=poly_exp(f);
for(int &v:f) v=1ll*t*v%P;
f.resize(l);
std::rotate(f.begin(),f.begin()+l-i*k,f.end());
return f;
}
poly poly_shift(poly a,int k)
{
int l(a.size());
poly tr(l);
for(int i(0),j(1);i<l;++i,j=1ll*j*k%P) tr[i]=1ll*j*ifac[i]%P;
for(int i(0);i<l;++i) a[i]=1ll*fac[i]*a[i]%P;
std::reverse(a.begin(),a.end());
a=a*tr;a.resize(l);std::reverse(a.begin(),a.end());
for(int i(0);i<l;++i) a[i]=1ll*ifac[i]*a[i]%P;
return a;
}
}
using polynomial::poly;
using polynomial::init_poly_weights;
using polynomial::operator+;
using polynomial::operator*;
using polynomial::init_poly_weights;
using polynomial::poly_inv;
using polynomial::poly_ln;
using polynomial::poly_exp;
using polynomial::poly_pow;
using polynomial::poly_shift;
using polynomial::ifac;
using polynomial::fac;
using polynomial::inv;
constexpr int N(1e5+10),p(998244353),_2((p+1)/2);
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()
{
int D,n,m;std::cin>>D>>n>>m;init_poly_weights(D+1);
if(m*2>n){std::cout<<"0"<<std::endl;return 0;}
int l(std::min(D,n-2*m));
poly F(D+1),G(D+1);
for(int i(D-l);i<=D;++i) F[i]=1ll*fac[D]*ifac[i]%p;
for(int i(0);i<=D;++i) G[i]=(i&1)?p-ifac[i]:ifac[i];
F=F*G;F.resize(D+1);
for(int j(D),t(1);j>=0;--j,t=2*t%p) F[j]=1ll*F[j]*t%p*ifac[D-j]%p;
// for(int v:F) std::cout<<v<<" ";std::cout<<std::endl;
F=poly_shift(F,1);
// for(int v:F) std::cout<<v<<" ";std::cout<<std::endl;
static int ps[N],val[N];int pc(0);static bool vis[N];val[1]=1;
for(int i(2);i<=D;++i)
{
if(!vis[i]) val[i]=fp(i,n),ps[++pc]=i;
for(int j(1);j<=pc && ps[j]*i<=D;++j)
{
val[ps[j]*i]=1ll*val[ps[j]]*val[i]%p;
vis[ps[j]*i]=true;
if((i%ps[j])==0) break;
}
}
int ans(0);
for(int i(0);i<=D;++i)
{
int t(D-i*2);
if(t<0 && n&1) ans=(ans+1ll*(p-val[std::abs(t)])*F[i])%p;
else ans=(ans+1ll*val[std::abs(t)]*F[i])%p;
}
std::cout<<1ll*ans*fp(_2,D)%p<<std::endl;
return 0;
}
詳細信息
Test #1:
score: 4
Accepted
time: 2ms
memory: 3508kb
input:
2 7 3
output:
128
result:
ok 1 number(s): "128"
Test #2:
score: 4
Accepted
time: 2ms
memory: 3524kb
input:
2 20 9
output:
1048576
result:
ok 1 number(s): "1048576"
Test #3:
score: 4
Accepted
time: 0ms
memory: 3520kb
input:
99 97 30
output:
893559494
result:
ok 1 number(s): "893559494"
Test #4:
score: 4
Accepted
time: 2ms
memory: 3572kb
input:
100 97 29
output:
870441375
result:
ok 1 number(s): "870441375"
Test #5:
score: 4
Accepted
time: 2ms
memory: 3504kb
input:
97 100 16
output:
114531619
result:
ok 1 number(s): "114531619"
Test #6:
score: 4
Accepted
time: 2ms
memory: 3568kb
input:
98 98 38
output:
910698957
result:
ok 1 number(s): "910698957"
Test #7:
score: 4
Accepted
time: 2ms
memory: 3532kb
input:
100 99 30
output:
267167918
result:
ok 1 number(s): "267167918"
Test #8:
score: 4
Accepted
time: 1ms
memory: 3896kb
input:
4000 3998 602
output:
267823033
result:
ok 1 number(s): "267823033"
Test #9:
score: 4
Accepted
time: 3ms
memory: 3916kb
input:
3999 3998 478
output:
7661427
result:
ok 1 number(s): "7661427"
Test #10:
score: 4
Accepted
time: 3ms
memory: 3976kb
input:
4000 3999 18
output:
46680613
result:
ok 1 number(s): "46680613"
Test #11:
score: 4
Accepted
time: 3ms
memory: 3900kb
input:
4000 3998 683
output:
689956672
result:
ok 1 number(s): "689956672"
Test #12:
score: 4
Accepted
time: 3ms
memory: 3912kb
input:
3998 3998 1743
output:
625630497
result:
ok 1 number(s): "625630497"
Test #13:
score: 4
Accepted
time: 2ms
memory: 3504kb
input:
300 999999997 499999880
output:
311178114
result:
ok 1 number(s): "311178114"
Test #14:
score: 4
Accepted
time: 2ms
memory: 3540kb
input:
297 999999999 499999955
output:
111728734
result:
ok 1 number(s): "111728734"
Test #15:
score: 4
Accepted
time: 1ms
memory: 3576kb
input:
298 999999998 499999978
output:
873407954
result:
ok 1 number(s): "873407954"
Test #16:
score: 4
Accepted
time: 40ms
memory: 16520kb
input:
100000 999999998 0
output:
403169128
result:
ok 1 number(s): "403169128"
Test #17:
score: 4
Accepted
time: 35ms
memory: 16512kb
input:
99999 100000 1
output:
520922757
result:
ok 1 number(s): "520922757"
Test #18:
score: 4
Accepted
time: 34ms
memory: 16524kb
input:
99998 99998 2
output:
776350879
result:
ok 1 number(s): "776350879"
Test #19:
score: 4
Accepted
time: 32ms
memory: 16624kb
input:
99998 999999998 499972261
output:
805937760
result:
ok 1 number(s): "805937760"
Test #20:
score: 4
Accepted
time: 42ms
memory: 16620kb
input:
99997 999999999 499975678
output:
265933807
result:
ok 1 number(s): "265933807"
Test #21:
score: 4
Accepted
time: 35ms
memory: 16528kb
input:
100000 1000000000 499958129
output:
59384653
result:
ok 1 number(s): "59384653"
Test #22:
score: 4
Accepted
time: 44ms
memory: 16532kb
input:
99998 999999999 499978565
output:
897679746
result:
ok 1 number(s): "897679746"
Test #23:
score: 4
Accepted
time: 37ms
memory: 16520kb
input:
100000 999999999 499970692
output:
169325977
result:
ok 1 number(s): "169325977"
Test #24:
score: 4
Accepted
time: 36ms
memory: 16596kb
input:
99997 1000000000 499976402
output:
562099965
result:
ok 1 number(s): "562099965"
Test #25:
score: 4
Accepted
time: 39ms
memory: 16556kb
input:
99997 1000000000 499978285
output:
681053406
result:
ok 1 number(s): "681053406"
Extra Test:
score: 0
Extra Test Passed