Submission #64013380

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

constexpr int mod = 998244353;
int Add(int x, int y){ return (x + y) >= mod ? (x + y - mod) : (x + y); }
int Sub(int x, int y){ return (x - y) < 0 ? (x - y + mod) : (x - y); }
int Mul(int x, int y){ return 1ll * x * y % mod; }

int fastpow(int x, int y){
    int ret = 1;
    for(;y;y>>=1,x=Mul(x, x)){ if(y & 1) ret = Mul(ret, x); }
    return ret;
}

const int N = 505, N_ = N * N;

int h(int x){ return (x * (x - 1)) >> 1; }

int n, m, f[N], pw[N_], pw2[N_], fact[N], inv[N];

int binom(int n, int m){ return n < m ? 0 : Mul(fact[n], Mul(inv[m], inv[n - m])); }

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> m;
    fact[0] = inv[0] = 1;
    for(int i=1;i<=n;i++) fact[i] = Mul(fact[i - 1], i), inv[i] = fastpow(fact[i], mod - 2);
    int ans = Mul(Sub(n, Add(m, 1)), fastpow(m, h(n)));
    pw[0] = pw2[0] = 1;
    for(int i=1;i<=n*n;i++) pw[i] = Mul(pw[i - 1], m);
    for(int k=1;k<=m;k++){
        for(int i=1;i<=n*n;i++) pw2[i] = Mul(pw2[i - 1], m - k);
        for(int N=1;N<=n;N++){
            f[N] = pw[h(N)];
            for(int i=1;i<N;i++){
                int tmp = Mul(binom(N - 1, i - 1), f[i]);
                tmp = Mul(tmp, Mul(pw[h(N - i)], pw2[i * (N - i)]));
                f[N] = Sub(f[N], tmp);
            }
            int ret = Mul(pw2[N * (n - N)], pw[h(n - N)]);
            ans = Add(ans, Mul(f[N], Mul(binom(n, N), ret)));
        }
    }
    cout << ans << '\n';
    return 0;
}

// Written by xiezheyuan

Submission Info

Judge Result