結果
問題 | No.2511 Mountain Sequence |
ユーザー |
![]() |
提出日時 | 2023-10-28 13:59:32 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,167 ms / 2,000 ms |
コード長 | 3,777 bytes |
コンパイル時間 | 4,556 ms |
コンパイル使用メモリ | 291,684 KB |
実行使用メモリ | 12,048 KB |
最終ジャッジ日時 | 2024-09-25 16:25:12 |
合計ジャッジ時間 | 25,033 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 32 |
ソースコード
#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^nFPS<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;}