結果
問題 | No.1302 Random Tree Score |
ユーザー |
![]() |
提出日時 | 2024-01-11 08:52:31 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 315 ms / 3,000 ms |
コード長 | 7,679 bytes |
コンパイル時間 | 3,697 ms |
コンパイル使用メモリ | 242,760 KB |
最終ジャッジ日時 | 2025-02-18 17:07:43 |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 14 |
ソースコード
#include<bits/stdc++.h>#include<atcoder/modint>#include<atcoder/convolution>using namespace std;using namespace atcoder;int get_primitive_root(int mod){if (mod==167772161)return 3;if (mod==469762049)return 3;if (mod==754974721)return 11;if (mod==998244353)return 3;if (mod==1224736769)return 3;assert(0);return 0;}template<typename T>void bit_rev(vector<T>&a){int n=a.size();for(int i=0,j=1;j<n-1;j++){for(int k=n>>1;k>(i^=k);k>>=1);if(i<j)swap(a[i],a[j]);}}template<typename mint>void NTT(vector<mint>&f, bool ordered=false){constexpr int mod=mint::mod();mint primitive_root=get_primitive_root(mod);int n=f.size();for(int m=n;m>1;m>>=1){mint omega=primitive_root.pow((mod-1)/m);for(int s=0;s<n/m;s++){mint w=1;for(int i=0;i<m/2;i++){mint l=f[s*m+i];mint r=f[s*m+i+m/2];f[s*m+i]=l+r;f[s*m+i+m/2]=(l-r)*w;w*=omega;}}}if(ordered)bit_rev(f);}template<typename mint>void INTT(vector<mint>&f, bool ordered=false){constexpr int mod=mint::mod();mint primitive_root=get_primitive_root(mod);if(ordered)bit_rev(f);int n=f.size();for(int m=2;m<=n;m<<=1){mint omega=primitive_root.pow((mod-1)/m).inv();for(int s=0;s<n/m;s++){mint w=1;for(int i=0;i<m/2;i++){mint l=f[s*m+i];mint r=f[s*m+i+m/2]*w;f[s*m+i]=l+r;f[s*m+i+m/2]=l-r;w*=omega;}}}}template<typename mint>struct FormalPowerSeries:vector<mint>{using FPS=FormalPowerSeries;using vector<mint>::vector;using vector<mint>::operator=;FPS &operator+=(const mint&r){if(this->empty())this->resize(1);(*this)[0]+=r;return *this;}FPS &operator-=(const mint&r){if(this->empty())this->resize(1);(*this)[0]-=r;return *this;}FPS &operator*=(const mint&r){for(mint &x:*this)x*=r;return *this;}FPS &operator/=(const mint&r){mint r_=r.inv();for(mint &x:*this)x*=r_;return *this;}FPS operator+(const mint&r)const{return FPS(*this)+=r;}FPS operator-(const mint&r)const{return FPS(*this)-=r;}FPS operator*(const mint&r)const{return FPS(*this)*=r;}FPS operator/(const mint&r)const{return FPS(*this)/=r;}FPS operator+=(const FPS&r){if(this->size()<r.size())this->resize(r.size());for(int i=0;i<(int)r.size();i++)(*this)[i]+=r[i];return *this;}FPS operator-=(const FPS&r){if(this->size()<r.size())this->resize(r.size());for(int i=0;i<(int)r.size();i++)(*this)[i]-=r[i];return *this;}FPS operator*=(const FPS&r){*this=convolution(*this,r);return *this;}FPS operator/=(const FPS&r){*this*=r.inv();return *this;}FPS operator%=(const FPS&r){*this-=*this/r*r;shrink();return *this;}FPS operator+(const FPS&r)const{return FPS(*this)+=r;}FPS operator-(const FPS&r)const{return FPS(*this)-=r;}FPS operator*(const FPS&r)const{return FPS(*this)*=r;}FPS operator/(const FPS&r)const{return FPS(*this)/=r;}FPS operator%(const FPS&r)const{return FPS(*this)%=r;}FPS pre(int n)const{return FPS(this->begin(),this->begin()+min((int)this->size(),n));}FPS rev(int n=-1)const{FPS res=*this;if(n!=-1)res.resize(n,0);return FPS(res.rbegin(),res.rend());}void shrink(){while(!this->empty()&&this->back()==0)this->pop_back();}FPS operator<<(int n)const{FPS res=*this;res.insert(res.begin(),n,0);return res;}FPS operator>>(int n)const{if((int)this->size()<=n)return{};FPS res=*this;res.erase(res.begin(),res.begin()+n);return res;}mint operator()(const mint&r){mint r_=0,powr=1;for(int i=0;i<this->size();i++){for(auto x:*this){r_+=x*powr;powr*=r;}return r_;}}FPS inv(int n=-1)const{assert(!this->empty());assert((*this)[0]!=0);if(n==-1)n=this->size();FPS res={(*this)[0].inv()};for(int d=1;d<n;d<<=1){vector<mint>f=pre(2*d);vector<mint>g=res;f.resize(2*d);g.resize(2*d);NTT(f);NTT(g);for(int i=0;i<2*d;i++)f[i]*=g[i];INTT(f);for(int i=0;i<d;i++)f[i]=0;NTT(f);for(int i=0;i<2*d;i++)f[i]*=g[i];INTT(f);res.resize(2*d);mint coeff=mint(2*d).inv().pow(2);for(int i=d;i<2*d;i++)res[i]-=f[i]*coeff;}return res.pre(n);}FPS exp(int n=-1)const{assert((*this)[0]==0);if(n==-1)n=this->size();FPS res={1};for(int i=1;i<n;i<<=1){res=(res*(this->pre(i<<1)+mint(1)-res.log(i<<1))).pre(i<<1);}return res;}FPS log(int n=-1)const{assert((*this)[0]==1);if(n==-1)n=this->size();return FPS((diff()*inv(n)).pre(n-1)).integral();}FPS pow(long long k, int n=-1)const{if(n==-1)n=this->size();if(k==0){FPS res(n);res[0]=1;return res;}FPS res=*this;int cnt0=0;while(cnt0<res.size()&&res[cnt0]==0)cnt0++;if (cnt0>(n-1)/k){FPS res(n);return res;}res=res>>cnt0;n-=cnt0*k;res=((res/res[0]).log(n)*k).exp(n)*res[0].pow(k);res=res<<(cnt0*k);return res;}FPS diff()const{int n=this->size();FPS res(max(0,n-1));for(int i=1;i<=(int)res.size();i++){res[i-1]=(*this)[i]*i;}return res;}FPS integral()const{FPS res(this->size()+1);res[0]=0;for(int i=0;i<(int)res.size()-1;i++){res[i+1]=(*this)[i]/(i+1);}return res;}vector<mint>multipoint_evaluation(vector<mint>&x){if(x.empty())return{};int m=x.size(),n=1;if(this->size()==0){return vector<mint>(m,0);}if(this->size()==1){return vector<mint>(m,(*this)[0]);}while(m>n)n<<=1;vector<FPS>f(n<<1,FPS({mint(1)}));for(int i=0;i<m;i++)f[i+n]=FPS({-x[i],mint(1)});for(int i=n-1;i>0;i--)f[i]=f[i<<1]*f[(i<<1)|1];f[1]=(*this)%f[1];for(int i=2;i<n+m;i++)f[i]=f[i>>1]%f[i];vector<mint>res(m);for(int i=0;i<m;i++)res[i]=(f[i+n].empty()?mint(0):f[i+n][0]);return res;}};using mint=modint998244353;using FPS=FormalPowerSeries<mint>;int N;int main(){ios::sync_with_stdio(false);cin.tie(nullptr);cin>>N;FPS f(2*N);mint fact=1;for(int i=1;i<=N;i++){f[i]=i*fact.inv();fact*=i;}f=f.pow(N);mint ans=f[2*N-2];mint invN=mint(N).inv();for(int i=1;i<=N-2;i++){ans*=i;ans*=invN;}cout << ans.val() << endl;}