結果
問題 | No.1967 Sugoroku Optimization |
ユーザー |
![]() |
提出日時 | 2022-06-03 22:15:33 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 611 ms / 2,000 ms |
コード長 | 862 bytes |
コンパイル時間 | 4,084 ms |
コンパイル使用メモリ | 231,256 KB |
実行使用メモリ | 34,688 KB |
最終ジャッジ日時 | 2024-09-21 02:49:54 |
合計ジャッジ時間 | 9,224 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 21 |
ソースコード
#include <bits/stdc++.h>using namespace std;#include <atcoder/all>using namespace atcoder;using ll=long long;using Graph=vector<vector<int>>;#define INF 1000000000000000000#define MOD 998244353#define MAX 1000000ll modpow(ll a,ll n,ll mod=MOD){ll res=1;a%=mod;while(n>0){if(n&1){res=(res*a)%mod;}a=(a*a)%mod;n>>=1;}return res;}ll modinv(ll a,ll mod=MOD){return modpow(a,mod-2,mod);}int main(){int N,K;cin>>N>>K;vector<vector<ll>> dp(K+1,vector<ll>(N+1,0));for(int i=0;i<=K;i++){dp[i][N]=1;}for(int i=K-1;i>=0;i--){vector<ll> sum=dp[i+1];for(int j=1;j<=N;j++){sum[j]+=sum[j-1];sum[j]%=MOD;}//dp[i][0]=sum[N]*modinv(N)%MOD;for(int j=0;j<N;j++){dp[i][j]=((sum[N]+MOD-sum[j])%MOD)*modinv(N-j)%MOD;}}cout<<dp[0][0]<<'\n';}