1528B - Kavi on Pairing Duty - CodeForces Solution

#include<bits/stdc++.h>
//#include<ext/pb_ds/assoc_container.hpp>
//#include<ext/pb_ds/tree_policy.hpp>
#define ll unsigned long long
#define int long long
#define lld long double
#define mod 998244353ll
#define inf (1LL<<60)
#define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL)
using namespace std;
//using namespace __gnu_pbds;
//typedef tree<pair<int,int>,null_type,less<pair<int,int>>,rb_tree_tag,tree_order_statistics_node_update>ordered_set;//find_by_order // order_of_key
//typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>ordered_set;//find by order // order of key
int expo(ll a, ll b) {a %= mod; ll res = 1; while (b > 0) {if (b & 1) res = (res * a) % mod; a = (a * a) % mod; b >>= 1;} return res;}
double eps = 1e-7;
const int N = 2e6+10;
int dp[N];
int fac[N];
int sum[N];
int solve(int n){
    if(n==0){
        return 0;
    }
    if(dp[n]!=-1)return dp[n];
    int ans=(sum[n-1]);
    //cout<<ans<<" ";
    ans=(ans+fac[2*n])%mod;
    //cout<<ans<<" ";
    sum[n]=(sum[n-1]+ans)%mod;
    //cout<<"n:"<<n<<" "<<sum[n-1]<<" sum[n]:"<<sum[n]<<endl;
    return dp[n]=ans;
}
int32_t main() {
    fast_io;int t=1;//cin >> t;
    fac[0]=0;
    fac[1]=1;
    for(int i=2;i<N;i+=2){
        for(int j=2*i;j<N;j+=i){
            fac[j]=(fac[j]+1)%mod;
        }
    }
    sum[0]=1;
    for(int T=0;T<t;T++){
        int n;
        cin>>n;
        memset(dp,-1,sizeof(dp));
        for(int i=1;i<=n;i++){
            solve(i);
        }
        cout<<solve(n)<<endl;   

    }
    return 0;
}