Submission #36057704

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using ld = long double;
using pll = pair<ll, ll>;
// and so on
const ll BigN = 998244353;
ll dp[1001][1001];
ll modpow(ll a, ll n) {
    ll ret = 1;
    while (n > 0) {
        if (n & 1) {
            ret = (ret * a) % BigN;
        }
        a = (a * a) % BigN;
        n >>= 1;
    }
    return ret;
}
ll modinv(ll p) { return modpow(p, BigN - 2); }

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int N, M, K;
    cin >> N >> M >> K;
    dp[0][0] = 1;
    ll minv = modinv(M);
    ll ans = 0;
    for (int i = 1; i <= K; i++) {
        for (int j = 0; j < N; j++) {
            for (int k = 1; k <= M; k++) {
                int np = j + k;
                np -= (j + k > N ? 2*(j + k - N) : 0);
                dp[i][np] += (dp[i - 1][j] * minv) % BigN;
                dp[i][np] %= BigN;
            }
        }
        ans += dp[i][N];
        ans %= BigN;
    }
    cout << ans;
}

Submission Info

Judge Result