結果
問題 | No.1967 Sugoroku Optimization |
ユーザー |
![]() |
提出日時 | 2022-03-27 00:48:26 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 547 ms / 2,000 ms |
コード長 | 2,622 bytes |
コンパイル時間 | 1,730 ms |
コンパイル使用メモリ | 171,028 KB |
実行使用メモリ | 34,560 KB |
最終ジャッジ日時 | 2024-09-21 02:25:01 |
合計ジャッジ時間 | 6,969 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 21 |
ソースコード
#include <bits/stdc++.h>using namespace std;#define ll long long#define rep(i,n) for(int i=0;i<n;i++)#define rrep(i,n) for(int i=n-1;i>=0;i--)#define riano_ std::ios::sync_with_stdio(false);std::cin.tie(nullptr)const ll mod = 998244353;template<uint64_t mod>struct modint{uint64_t val;constexpr modint(const int64_t val_=0) noexcept:val((val_%int64_t(mod)+int64_t(mod))%int64_t(mod)){}constexpr modint operator-() const noexcept{return modint(*this)=mod-val;}constexpr modint operator+(const modint rhs) const noexcept{return modint(*this)+=rhs;}constexpr modint operator-(const modint rhs) const noexcept{return modint(*this)-=rhs;}constexpr modint operator*(const modint rhs) const noexcept{return modint(*this)*=rhs;}constexpr modint operator/(const modint rhs) const noexcept{return modint(*this)/=rhs;}constexpr modint &operator+=(const modint rhs) noexcept{val+=rhs.val;val-=((val>=mod)?mod:0);return (*this);}constexpr modint &operator-=(const modint rhs) noexcept{val+=((val<rhs.val)?mod:0);val-=rhs.val;return (*this);}constexpr modint &operator*=(const modint rhs) noexcept{val=val*rhs.val%mod;return (*this);}constexpr modint &operator/=(modint rhs) noexcept{uint64_t ex=mod-2;modint now=1;while(ex){now*=((ex&1)?rhs:1);rhs*=rhs,ex>>=1;}return (*this)*=now;}modint & operator++(){val++;if (val == mod) val = 0;return *this;}modint operator++(int){modint<mod> res = *this;++*this;return res;}constexpr bool operator==(const modint rhs) noexcept{return val==rhs.val;}constexpr bool operator!=(const modint rhs) noexcept{return val!=rhs.val;}friend constexpr ostream &operator<<(ostream& os,const modint x) noexcept{return os<<(x.val);}friend constexpr istream &operator>>(istream& is,modint& x) noexcept{uint64_t t;is>>t,x=t;return is;}};typedef modint<mod> mint;#define vm(n,i) vector<mint>(n,i)#define v2m(n,m,i) vector<vector<mint>>(n,vm(m,i))int main(){riano_;ll N,K; cin >> N >> K;auto dp = v2m(K+1,N+1,0);rep(i,K+1) dp[i][N] = 1;rep(i,K){mint sum = 0,cnt = 0;rrep(j,N){sum += dp[i][j+1]; cnt += 1;dp[i+1][j] = sum/cnt;}}cout << dp[K][0] << endl;}