結果
問題 | No.2511 Mountain Sequence |
ユーザー | momoyuu |
提出日時 | 2023-10-28 13:59:32 |
言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 1,194 ms / 2,000 ms |
コード長 | 3,777 bytes |
コンパイル時間 | 4,765 ms |
コンパイル使用メモリ | 291,160 KB |
実行使用メモリ | 11,952 KB |
最終ジャッジ日時 | 2023-10-28 13:59:59 |
合計ジャッジ時間 | 26,633 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,348 KB |
testcase_01 | AC | 2 ms
4,348 KB |
testcase_02 | AC | 47 ms
4,348 KB |
testcase_03 | AC | 1,089 ms
11,856 KB |
testcase_04 | AC | 200 ms
5,304 KB |
testcase_05 | AC | 515 ms
7,960 KB |
testcase_06 | AC | 48 ms
4,348 KB |
testcase_07 | AC | 1,153 ms
11,092 KB |
testcase_08 | AC | 222 ms
5,860 KB |
testcase_09 | AC | 399 ms
7,692 KB |
testcase_10 | AC | 1,086 ms
11,116 KB |
testcase_11 | AC | 541 ms
7,108 KB |
testcase_12 | AC | 211 ms
7,892 KB |
testcase_13 | AC | 1,112 ms
10,952 KB |
testcase_14 | AC | 536 ms
7,696 KB |
testcase_15 | AC | 466 ms
7,040 KB |
testcase_16 | AC | 112 ms
4,704 KB |
testcase_17 | AC | 1,183 ms
10,688 KB |
testcase_18 | AC | 1,194 ms
11,132 KB |
testcase_19 | AC | 1,099 ms
11,560 KB |
testcase_20 | AC | 943 ms
11,904 KB |
testcase_21 | AC | 1,163 ms
10,604 KB |
testcase_22 | AC | 1,158 ms
11,060 KB |
testcase_23 | AC | 2 ms
4,348 KB |
testcase_24 | AC | 2 ms
4,348 KB |
testcase_25 | AC | 2 ms
4,348 KB |
testcase_26 | AC | 3 ms
4,348 KB |
testcase_27 | AC | 3 ms
4,348 KB |
testcase_28 | AC | 2 ms
4,348 KB |
testcase_29 | AC | 967 ms
11,944 KB |
testcase_30 | AC | 955 ms
11,952 KB |
testcase_31 | AC | 959 ms
11,864 KB |
testcase_32 | AC | 960 ms
10,948 KB |
testcase_33 | AC | 456 ms
7,900 KB |
testcase_34 | AC | 955 ms
11,648 KB |
ソースコード
#include<bits/stdc++.h> using namespace std; using ll = long long; #include<atcoder/modint> #include<atcoder/convolution> using mint = atcoder::modint998244353; #define conv(a,b) atcoder::convolution(a,b) ostream& operator<<(ostream& os, const mint& m){ os << m.val(); return os; } template < typename mint > struct FPS:vector<mint>{ FPS(){} FPS(int n){ this->resize(n); } FPS(vector<mint>a){ *this = a; } FPS &operator+=(const FPS&r){ if(r.size()>this->size()) this->resize(r.size()); for(int i = 0;i<(int)r.size();i++) (*this)[i] += r[i]; return *this; } FPS &operator+=(const mint&r){ if(this->empty()) this->resize(1); (*this)[0] += r; return *this; } FPS &operator-=(const FPS&r){ if(r.size()>this->size()) this->resize(r.size()); for(int i = 0;i<(int)r.size();i++) (*this)[i] -= r[i]; return *this; } FPS &operator-=(const mint&r){ if(this->empty()) this->resize(1); (*this)[0] -= r; return *this; } FPS &operator*=(const FPS&r){ vector<mint> nxt = conv(*this,r); this->resize(nxt.size()); for(int i = 0;i<nxt.size();i++) (*this)[i] = nxt[i]; return *this; } FPS &operator*=(const mint&r){ for(int i = 0;i<(int)this->size();i++) (*this)[i] *= r; return *this; } FPS operator+(const FPS&r) const {return FPS(*this)+=r;} FPS operator+(const mint&r) const {return FPS(*this)+=r;} FPS operator-(const FPS&r) const {return FPS(*this)-=r;} FPS operator-(const mint&r) const {return FPS(*this)-=r;} FPS operator*(const FPS&r) const {return FPS(*this)*=r;} void print(){ for(int i = 0;i<(int)this->size();i++){ if(i) cout<<" "; cout<<(*this)[i]; } cout<<endl; } int deg(){return (int)this->size()-1;} // f^-1 mod x^n FPS<mint> inv(int n){ assert((*this)[0].val()!=0); FPS<mint> g(1); g[0] = 1/(*this)[0]; ll now = 1; FPS<mint> tmp(1); tmp[0] = 2; while(now<n){ g = g * (tmp-g*(*this)); now <<= 1; if(g.size()>now) g.resize(now); } g.resize(n); return g; } FPS<mint> diff(){ FPS<mint>g(this->size()-1); for(int i = 0;i+1<this->size();i++) g[i] = mint(i+1) * (*this)[i+1]; return g; } FPS<mint> integral(){ FPS<mint>g(this->size()+1); g[0] = 0; for(int i = 1;i<=this->size();i++) g[i] = (*this)[i-1] / mint(i); return g; } FPS<mint> log(int n){ assert((*this)[0].val()==1); return ((*this).diff() * (*this).inv(n-1)).integral(); } FPS<mint> exp(int n){ assert((*this)[0].val()==0); FPS<mint> g(1); g[0] = 1; ll now = 1; FPS<mint> tmp(1); tmp[0] = 1; while(now<n){ g = g * ((*this) + tmp - g.log(now<<1)); now <<= 1; if(g.size()>now) g.resize(now); } return g; } }; template < typename mint > FPS<mint> pow(FPS<mint>&a,ll k,int n){ FPS<mint> ans(n+1); ans[0] += 1; FPS<mint> tmp = a; tmp.resize(n+1); while(k){ if(k&1){ ans *= tmp; ans.resize(n+1); } tmp *= tmp; tmp.resize(n+1); k>>=1; } return ans; } int main(){ cin.tie(nullptr); ios::sync_with_stdio(false); int n,m; cin>>n>>m; FPS<mint> y(3); y[0] = 1; y[1] = 2; y[2] = 1; FPS<mint> f(1); f[0] = 1; f -= pow(y,m,n); FPS<mint> g(2); g[0] = -2; g[1] = -1; f *= g.inv(n); cout<<f[n]<<endl; }