結果
問題 | No.1100 Boxes |
ユーザー |
![]() |
提出日時 | 2024-02-12 17:50:11 |
言語 | C++17(clang) (17.0.6 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 90 ms / 2,000 ms |
コード長 | 14,186 bytes |
コンパイル時間 | 4,745 ms |
コンパイル使用メモリ | 185,504 KB |
実行使用メモリ | 10,140 KB |
最終ジャッジ日時 | 2024-09-28 18:09:02 |
合計ジャッジ時間 | 7,017 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 36 |
ソースコード
#include <bits/stdc++.h>using namespace std;#if __has_include(<atcoder/all>)#include <atcoder/all>using namespace atcoder;template<int mod>istream &operator>>(istream &is,static_modint<mod> &a){long long b;is>>b;a=b;return is;}istream &operator>>(istream &is,modint &a){long long b;cin>>b;a=b;return is;}#endif#ifdef LOCAL#include "debug.h"#else#define debug(...) static_cast<void>(0)#define debugg(...) static_cast<void>(0)template<typename T1,typename T2>ostream &operator<<(ostream &os,const pair<T1,T2>&p){os<<p.first<<' '<<p.second;return os;}#endifusing ll=long long;using ull=unsigned long long;using P=pair<ll,ll>;template<typename T>using minque=priority_queue<T,vector<T>,greater<T>>;template<typename T>bool chmax(T &a,const T &b){return (a<b?(a=b,true):false);}template<typename T>bool chmin(T &a,const T &b){return (a>b?(a=b,true):false);}template<typename T1,typename T2>istream &operator>>(istream &is,pair<T1,T2>&p){is>>p.first>>p.second;return is;}template<typename T>istream &operator>>(istream &is,vector<T> &a){for(auto &i:a)is>>i;return is;}template<typename T1,typename T2>void operator++(pair<T1,T2>&a,int n){a.first++,a.second++;}template<typename T1,typename T2>void operator--(pair<T1,T2>&a,int n){a.first--,a.second--;}template<typename T>void operator++(vector<T>&a,int n){for(auto &i:a)i++;}template<typename T>void operator--(vector<T>&a,int n){for(auto &i:a)i--;}#define reps(i,a,n) for(int i=(a);i<(n);i++)#define rep(i,n) reps(i,0,n)#define all(x) x.begin(),x.end()#define pcnt(x) __builtin_popcountll(x)ll myceil(ll a,ll b){return (a+b-1)/b;}template<typename T,size_t n,size_t id=0>auto vec(const int (&d)[n],const T &init=T()){if constexpr (id<n)return vector(d[id],vec<T,n,id+1>(d,init));else return init;}void SOLVE();int main(){ios::sync_with_stdio(false);cin.tie(nullptr);#ifdef LOCALclock_t start=clock();#endifint testcase=1;//cin>>testcase;for(int i=0;i<testcase;i++){SOLVE();}#ifdef LOCALcerr<<"time:";cerr<<(clock()-start)/1000;cerr<<"ms\n";#endif}constexpr int primitive_root(int x){if(x==998244353)return 3;return -1;}constexpr int countr_zero(unsigned int n){int ret=0;while(!(n&(1<<ret)))ret++;return ret;}template<typename T>struct ntt_root{static constexpr int rank2=countr_zero(T::mod()-1);int g=primitive_root(T::mod());array<T,rank2+1>root,invroot;array<T,max(0,rank2-1)>rate2,invrate2;array<T,max(0,rank2-2)>rate3,invrate3;ntt_root(){root[rank2]=T::raw(g).pow((T::mod())>>rank2);invroot[rank2]=root[rank2].inv();for(int i=rank2-1;i>=0;i--){root[i]=root[i+1]*root[i+1];invroot[i]=invroot[i+1]*invroot[i+1];}{T prod=1,invprod=1;rep(i,rank2-1){rate2[i]=root[i+2]*prod;invrate2[i]=invroot[i+2]*invprod;prod*=invroot[i+2];invprod*=root[i+2];}}{T prod=1,invprod=1;rep(i,rank2-2){rate3[i]=root[i+3]*prod;invrate3[i]=invroot[i+3]*invprod;prod*=invroot[i+3];invprod*=root[i+3];}}}};template<typename T>void dft(vector<T>&a){int n=a.size();static const ntt_root<T> r;int h=countr_zero(n);ull mod2=(ull)T::mod()*T::mod();int len=0;while(len<h){if(h-len==1){T rot=1;rep(s,1<<len){int of=s*2;T u=a[of],v=a[of+1]*rot;a[of]=u+v;a[of+1]=u-v;if(s+1!=1<<len)rot*=r.rate2[__builtin_ctz(~(unsigned int)s)];}len++;}else{int p=1<<(h-len-2);T rot=1,imag=r.root[2];rep(s,1<<len){T rot2=rot*rot,rot3=rot*rot2;int of=s<<(h-len);rep(i,p){ull a0=a[i+of].val(),a1=(ull)a[i+of+p].val()*rot.val(),a2=(ull)a[i+of+p*2].val()*rot2.val(),a3=(ull)a[i+of+p*3].val()*rot3.val();ull m=(ull)T(a1+mod2-a3).val()*imag.val();ull k=mod2-a2;a[i+of]=a0+a2+a1+a3;a[i+of+p]=a0+a2+(mod2*2-a1-a3);a[i+of+p*2]=a0+k+m;a[i+of+p*3]=a0+k+(mod2-m);}if(s+1!=1<<len)rot*=r.rate3[__builtin_ctz(~(unsigned int)s)];}len+=2;}}}template<typename T>void idft(vector<T>&a){int n=a.size();static const ntt_root<T> r;int h=countr_zero(n);ull mod2=(ull)T::mod()*T::mod();int len=h;while(len){if(len==1){int p=1<<(h-1);T rot=1;rep(i,p){T u=a[i],v=a[i+p];a[i]=u+v;a[i+p]=(ull)(u.val()-v.val()+T::mod())*rot.val();}len--;}else{int p=1<<(h-len);T rot=1,imag=r.invroot[2];rep(s,1<<(len-2)){T rot2=rot*rot,rot3=rot*rot2;int of=s<<(h-len+2);rep(i,p){ull a0=a[i+of].val(),a1=a[i+of+p].val(),a2=a[i+of+p*2].val(),a3=a[i+of+p*3].val();ull k=T((T::mod()+a2-a3)*imag.val()).val();a[i+of]=a0+a1+a2+a3;a[i+of+p]=(a0+T::mod()-a1+k)*rot.val();a[i+of+p*2]=(a0+a1+T::mod()*2-a2-a3)*rot2.val();a[i+of+p*3]=(a0+T::mod()*2-a1-k)*rot3.val();}if(s+1!=1<<(len-2))rot*=r.invrate3[countr_zero(~(unsigned int)s)];}len-=2;}}}template<typename T>vector<T>ntt_convolution(vector<T> a,vector<T> b){int n=a.size(),m=b.size(),s=n+m-1;if(min(n,m)<60){vector<T>ret(s,0);if(n<m)rep(i,m)rep(j,n)ret[i+j]+=a[j]*b[i];else rep(i,n)rep(j,m)ret[i+j]+=a[i]*b[j];return ret;}int z=1;while(z<=s)z*=2;a.resize(z,0);b.resize(z,0);dft(a),dft(b);vector<T>c(z);rep(i,z)c[i]=a[i]*b[i];idft(c);T g=T::raw(z).inv();rep(i,s)c[i]*=g;return {c.begin(),c.begin()+s};}template<typename T>vector<T> fps_inv(const vector<T> &a,int deg=-1){int n=a.size();if(deg==-1)deg=n;assert(a[0]!=T(0));vector<T> ret(deg);ret[0]=a[0].inv();for(int m=1;m<deg;m<<=1){vector<T> f(a.begin(),a.begin()+min(n,m*2));if(f.size()<m*2)f.resize(m*2,0);vector<T> g(ret);f.resize(m*2);dft(f);g.resize(m*2);dft(g);rep(i,m*2)f[i]*=g[i];idft(f);T inv=T::raw(m*2).inv();rep(i,m)f[i]=0;reps(i,m,m*2)f[i]*=inv;dft(f);rep(i,m*2)f[i]*=g[i];idft(f);rep(i,m*2)f[i]*=inv;reps(i,m,min(deg,m*2))ret[i]-=f[i];}return ret;}template<typename T>vector<T> fps_diff(const vector<T>&a){int n=a.size();vector<T>b(max(0,n-1));reps(i,1,n)b[i-1]=a[i]*i;return b;}template<typename T>vector<T> fps_integral(const vector<T>&a){int n=a.size();vector<T>b(n+1);b[0]=0;if(n)b[1]=1;reps(i,2,n+1)b[i]=-b[T::mod()%i]*(T::mod()/i);rep(i,n)b[i+1]*=a[i];return b;}template<typename T>vector<T> fps_log(const vector<T>&a,int deg=-1){int n=a.size();if(deg==-1)deg=n;vector<T>b=fps_integral(ntt_convolution(fps_diff(a),fps_inv(a,deg)));return {b.begin(),b.begin()+deg};}template<typename T>vector<T> fps_exp(const vector<T>&a,int deg=-1){assert(a.empty()||a[0]==0);int n=a.size();if(deg==-1)deg=n;vector<T>b{1};for(int m=1;m<deg;m*=2){vector<T>nxt=fps_log(b,m*2);rep(i,m*2)nxt[i]*=-1;rep(i,min(n,m*2))nxt[i]+=a[i];nxt[0]++;b=ntt_convolution(b,nxt);b.resize(m*2);}return {b.begin(),b.begin()+deg};}template<typename T>vector<T> fps_pow(vector<T> a,ll k,int deg=-1){int n=a.size();if(deg==-1)deg=n;if(k==0){vector<T>ret(deg,0);ret[0]=1;return ret;}int of=0;while(a[of]==0&&of!=n)of++;if(of==n)return vector<T>(deg,0);if(of!=0&&k>=deg)return vector<T>(deg,0);if(of*k>=deg)return vector<T>(deg,0);a.erase(a.begin(),a.begin()+of);n=a.size();T a0=a[0];T inv=a[0].inv();rep(i,n)a[i]*=inv;vector<T>lg=fps_log(a,deg);rep(i,deg)lg[i]*=k;vector<T>ep=fps_exp(lg,deg);T pw=a0.pow(k);rep(i,deg)ep[i]*=pw;vector<T>ret(deg,0);reps(i,of*k,deg)ret[i]=ep[i-of*k];return ret;}template<typename T>vector<T> fps_pow_sparse(const vector<T>&a,ll k,int deg=-1){int n=a.size();if(deg==-1)deg=n;vector<pair<int,T>>b;rep(i,n)if(a[i]!=0)b.emplace_back(i,a[i]);if(b.empty()){vector<T>ret(deg,0);if(k==0)ret[0]=1;return ret;}int of=b[0].first;T b0=b[0].second,inv=b0.inv();for(auto &i:b){i.first-=of;i.second*=inv;}b0=b0.pow(k);vector<T>ret(deg,0);ret[0]=1;rep(i,deg-1){T cu=0;for(auto [j,c]:b){if(i-j+1<0)continue;if(j==0)continue;cu-=c*ret[i-j+1]*(i-j+1);cu+=ret[i-j+1]*k*j*c;}ret[i+1]=cu/(i+1);}if(of){if(k>=deg||of*k>=deg)ret.assign(deg,0);else{ret.insert(ret.begin(),of*k,0);ret.resize(deg);}}for(auto &i:ret)i*=b0;return ret;}template<typename T>vector<T> fps_div_sparse(vector<T> a,const vector<T>&b,int deg=-1){int n=a.size(),m=b.size();if(deg==-1)deg=n;a.resize(deg,0);assert(b[0]!=0);vector<pair<int,T>>c;reps(i,1,m)if(b[i]!=0)c.emplace_back(i,b[i]);T v=b[0].inv();rep(i,deg){for(auto [j,e]:c){if(j>i)break;a[i]-=a[i-j]*e;}a[i]*=v;}return a;}template<typename T>inline vector<T> fps_inv_sparse(const vector<T>&a,int deg=-1){return fps_div_sparse({1},a,(deg==-1?a.size():deg));}template<typename T>vector<T>fps_fode_sparse(const vector<T>&a,const vector<T>&b){assert(a.size()==b.size());assert(a[0]==1);int n=a.size();vector<pair<int,T>>c,d;reps(i,1,n)if(a[i]!=0)c.emplace_back(i,a[i]);rep(i,n)if(b[i]!=0)d.emplace_back(i,b[i]);vector<T>f(n),df(n-1);f[0]=1;vector<T>inv(n);rep(i,n-1){T v=0;for(auto [j,x]:c){if(j>i)break;v+=x*df[i-j];}for(auto [j,x]:d){if(j>i)break;v+=x*f[i-j];}df[i]=-v;if(i==0)inv[1]=1;else inv[i+1]=-inv[T::mod()%(i+1)]*(T::mod()/(i+1));f[i+1]=df[i]*inv[i+1];}return f;}template<typename T>vector<T> fps_pow_sparse(const vector<T>&a,const vector<T>&b,ll k,ll l,int deg=-1){int n=a.size(),m=b.size();if(deg==-1)deg=n;assert(a[0]==1);vector<pair<int,T>>c,d;rep(i,n)if(a[i]!=0)c.emplace_back(i,a[i]);rep(i,m)if(b[i]!=0)d.emplace_back(i,b[i]);vector<T>f(deg,0),g(deg,0);for(auto [i,x]:c){for(auto [j,y]:d){if(i+j>=deg+1)continue;T z=x*y;if(i+j<deg)f[i+j]+=z;if(0<i+j&&i+j<=deg)g[i+j-1]-=z*(T(i)*k+T(j)*l);}}return fps_fode_sparse(f,g);}template<typename T>T bostan_mori(vector<T> p,vector<T> q,ll k){int z=1;int n=p.size(),m=q.size();while(z<m*2)z*=2;p.resize(z,0),q.resize(z,0);n=m-1;while(k){dft(p),dft(q);for(int i=0;i<z;i+=2)p[i]*=q[i+1];for(int i=1;i<z;i+=2)p[i]*=q[i-1];vector<T>v(z/2);rep(i,z/2)v[i]=q[i*2]*q[i*2+1];idft(p),idft(v);T inv=T::raw(z).inv(),inv2=inv*2;rep(i,z/2)v[i]*=inv2;vector<T>u(n);if(k&1)rep(i,n)u[i]=p[i*2+1]*inv;else rep(i,n)u[i]=p[i*2]*inv;u.resize(z,0),v.resize(z,0);swap(p,u),swap(q,v);k>>=1;}return p[0];}template<typename T>vector<T> berlekamp_massey(const vector<T>&s){const int n=s.size();vector<T>b,c;b.reserve(n+1),c.reserve(n+1);b.emplace_back(1),c.emplace_back(1);T y=1;reps(i,1,n+1){int l=c.size(),m=b.size();T x=0;rep(j,l)x+=c[j]*s[i-l+j];b.emplace_back(0);++m;if(x==0)continue;T f=x/y;if(l<m){auto c2=c;c.insert(c.begin(),m-l,0);rep(j,m)c[m-1-j]-=f*b[m-1-j];b=c2;y=x;}else{rep(j,m)c[l-1-j]-=f*b[m-1-j];}}reverse(all(c));return c;}template<typename T>T kth_term(vector<T>p,ll k){vector<T>q=berlekamp_massey(p);if(T::mod()==998244353){p=ntt_convolution(p,q);p.resize(q.size()-1);return bostan_mori(p,q,k);}auto convolution_naive=[](vector<T>&x,const vector<T>&y)->void {vector<T>temp(x.size()+y.size()-1,0);rep(i,x.size())rep(j,y.size())temp[i+j]+=x[i]*y[j];swap(x,temp);};convolution_naive(p,q);int n=q.size();p.resize(n-1);vector<T>mq(n);while(k){rep(i,n)mq[i]=q[i]*(i&1?-1:1);convolution_naive(p,mq);convolution_naive(q,mq);vector<T>u(n-1),v(n);if(k&1)rep(i,n-1)u[i]=p[i*2+1];else rep(i,n-1)u[i]=p[i*2];rep(i,n)v[i]=q[i*2];swap(p,u),swap(q,v);k>>=1;}if(p.empty())return 0;else return p[0];}template<typename T>struct factorial_table{private:int mod,capacity;vector<T>fact,factinv,inv;void resize(int n){fact.resize(n+1),factinv.resize(n+1),inv.resize(n+1);for(int i=capacity+1;i<=n;i++){fact[i]=fact[i-1]*i;inv[i]=-inv[mod%i]*(mod/i);factinv[i]=factinv[i-1]*inv[i];}capacity=n;}public:factorial_table():capacity(1),mod(T::mod()),fact{1,1},factinv{1,1},inv{0,1}{}T C(int n,int k){if(n<k)return 0;if(k<0)return 0;if(capacity<n)resize(n);return fact[n]*factinv[k]*factinv[n-k];}T P(int n,int k){if(n<k)return 0;if(k<0)return 0;if(capacity<n)resize(n);return fact[n]*factinv[n-k];}T H(int n,int k){return C(n+k-1,k);}T factorial(int n){if(capacity<n)resize(n);return fact[n];}T fact_inv(int n){if(capacity<n)resize(n);return factinv[n];}T S(ll n,int k){if(n<0)return 0;if(n<k)return 0;T ret=0;if(capacity<k)resize(k);rep(i,k+1){ret+=fact[k]*factinv[i]*factinv[k-i]*T::raw(i).pow(n)*((k-i)&1?-1:1);}return ret*factinv[k];}template<typename... INT>T O(INT...k){int n=0;for(int i:initializer_list<int>{k...}){if(i<0)return 0;n+=i;}if(capacity<n)resize(n);T ret=fact[n];for(int i:initializer_list<int>{k...})ret*=factinv[i];return ret;}};using mint=modint998244353;factorial_table<mint> table;void SOLVE(){int n,k;cin>>n>>k;vector<mint>f,g,h;//f*g=hg.resize(k+1);rep(i,k+1)g[i]=table.fact_inv(i);h.resize(k+1);rep(i,k+1)h[i]=table.fact_inv(i)*mint(i).pow(n);f=ntt_convolution(fps_inv(g),h);f.resize(k+1);vector<mint>e(k+1);for(int i=1;i<k+1;i+=2)e[i]=table.fact_inv(i);f=ntt_convolution(f,e);cout<<(f[k]*table.factorial(k)).val()<<endl;}