CF_722_B
123456789101112131415161718192021222324252627282930313233343536373839
// Problem: B. Kavi on Pairing Duty
// Contest: Codeforces - Codeforces Round #722 (Div. 1)
// URL: https://codeforces.com/contest/1528/problem/B
// Memory Limit: 256 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
#define FIO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
const ll mod = 998244353, maxn = 2e5 + 5;
inline ll add(ll a, ll b, ll m = mod) { return (((a % m) + (b % m)) % m); }
using namespace std ;
ll dp[1000001] ;
ll jumps( ll N ){
if( N == 1 || N == 0 )return 1LL;
if(dp[N] == - 1){
ll retVal = 0 ;
for(ll i = N-1 ; i > -1 ; i--){
retVal = add(retVal , jumps(i)) ;
}
dp[N] = add(retVal ,1LL) ;
}
return dp[N] ;
}
int main(){
FIO
ll n ;
cin>> n ;
memset(dp , -1 ,sizeof(dp)) ;
cout << jumps(n) << "\n" ;
return 0 ;
}
Cpp
INFO