結果
問題 | No.1302 Random Tree Score |
ユーザー | daddy |
提出日時 | 2022-12-12 01:05:23 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 908 ms / 3,000 ms |
コード長 | 3,807 bytes |
コンパイル時間 | 1,880 ms |
コンパイル使用メモリ | 176,368 KB |
実行使用メモリ | 29,676 KB |
最終ジャッジ日時 | 2024-10-15 20:03:03 |
合計ジャッジ時間 | 9,453 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,248 KB |
testcase_02 | AC | 163 ms
9,676 KB |
testcase_03 | AC | 380 ms
16,692 KB |
testcase_04 | AC | 151 ms
9,420 KB |
testcase_05 | AC | 908 ms
28,320 KB |
testcase_06 | AC | 740 ms
28,464 KB |
testcase_07 | AC | 149 ms
10,016 KB |
testcase_08 | AC | 425 ms
18,048 KB |
testcase_09 | AC | 713 ms
29,608 KB |
testcase_10 | AC | 754 ms
23,672 KB |
testcase_11 | AC | 143 ms
8,452 KB |
testcase_12 | AC | 844 ms
27,180 KB |
testcase_13 | AC | 2 ms
6,816 KB |
testcase_14 | AC | 705 ms
29,676 KB |
testcase_15 | AC | 822 ms
29,676 KB |
testcase_16 | AC | 2 ms
5,248 KB |
ソースコード
#pragma GCC optimization ("O3") #include <bits/stdc++.h> using namespace std; using ll = long long; using vec = vector<ll>; using mat = vector<vec>; using pll = pair<ll,ll>; #define INF (1LL<<61) //#define MOD 1000000007LL #define MOD 998244353LL #define EPS (1e-10) #define PR(x) cout << (x) << endl #define PS(x) cout << (x) << " " #define REP(i,m,n) for(ll (i)=(m),(i_len)=(n);(i)<(i_len);++(i)) #define FORE(i,v) for(auto (i):v) #define ALL(x) (x).begin(), (x).end() #define SZ(x) ((ll)(x).size()) #define REV(x) reverse(ALL((x))) #define ASC(x) sort(ALL((x))) #define DESC(x) {ASC((x)); REV((x));} #define BIT(s,i) (((s)>>(i))&1) #define pb push_back #define fi first #define se second template<class T> inline int chmin(T& a, T b) {if(a>b) {a=b; return 1;} return 0;} template<class T> inline int chmax(T& a, T b) {if(a<b) {a=b; return 1;} return 0;} class mint { public: ll x; mint(ll x=0) : x((x%MOD+MOD)%MOD) {} mint operator-() const {return mint(-x);} mint& operator+=(const mint& a) {if((x+=a.x)>=MOD) x-=MOD; return *this;} mint& operator-=(const mint& a) {if((x+=MOD-a.x)>=MOD) x-=MOD; return *this;} mint& operator*=(const mint& a) {(x*=a.x)%=MOD; return *this;} mint operator+(const mint& a) const {mint b(*this); return b+=a;} mint operator-(const mint& a) const {mint b(*this); return b-=a;} mint operator*(const mint& a) const {mint b(*this); return b*=a;} mint pow(ll t) const {if(!t) return 1; mint a=pow(t>>1); return (t&1?*this*a:a)*a;} mint inv() const {return pow(MOD-2);} mint& operator/=(const mint& a) {return *this*=a.inv();} mint operator/(const mint& a) const {mint b(*this); return b/=a;} }; istream &operator>>(istream& is, mint& a) {ll t; is>>t; a=t; return is;} ostream &operator<<(ostream& os, const mint& a) {return os<<a.x;} using mvec = vector<mint>; vec convolution(vec a, vec b) { struct LocalFunc { static ll modpow(ll a, ll n) { if(n == 0) return 1; ll t = modpow(a, n>>1); return (n&1?a*t%MOD:t)*t%MOD; } static void ntt(vec& a, bool rev=false) { ll i, j, k, l, p, q, r, s; ll size = a.size(); if(size == 1) return; vec b(size); r = rev?(MOD-1-(MOD-1)/size):(MOD-1)/size; s = modpow(3, r); vec kp(size/2+1, 1); for(i=0; i<size/2; ++i) kp[i+1] = kp[i]*s%MOD; for(i=1, l=size/2; i<size; i<<=1, l>>=1){ for(j=0, r=0; j<l; ++j, r+=i){ for(k=0, s=kp[i*j]; k<i; ++k){ p = a[k+r], q = a[k+r+size/2]; b[k+2*r] = (p+q<MOD)?(p+q):(p+q)-MOD; b[k+2*r+i] = s*((p>=q)?(p-q):(MOD-q+p))%MOD; } } swap(a, b); } if(rev){ s = modpow(size, MOD-2); for(i = 0; i < size; i++) a[i] = a[i]*s%MOD; } } }; ll size = a.size()+b.size()-1; ll t = 1; while(t < size) t <<= 1; vec A(t, 0), B(t, 0); for(ll i=0; i<a.size(); i++) A[i] = a[i]; for(ll i=0; i<b.size(); i++) B[i] = b[i]; LocalFunc::ntt(A); LocalFunc::ntt(B); for(ll i=0; i<t; i++) A[i] = A[i]*B[i]%MOD; LocalFunc::ntt(A, true); A.resize(max(a.size(), b.size())); return A; } vec ppow(vec A, ll n) { if(n == 0) return vec{1}; vec B = ppow(A, n>>1); return convolution((n&1?convolution(A, B):B), B); } int main() { ll N; cin >> N; vec A(N-1); mint t(1); REP(i,0,N-1) { if(i) t *= i; A[i] = (mint(i+1)/t).x; } mint ans = t*mint(N).pow(N-2).inv(); A = ppow(A, N); ans *= mint(A[N-2]); PR(ans.x); return 0; } /* */