提出 #61251939

---

ソースコード 拡げる

// Go in my style.
// Not afraid to dark.

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

clock_t sttime;
#define STCLOCK sttime = clock ();
#define TIMENOW fprintf (stderr, "\nNOW TIME COSSEMED: %0.4lf\n", 1.0 * (clock () - sttime) / CLOCKS_PER_SEC);
#define inline __inline__ __attribute__ ((always_inline))

#define int long long

namespace io {
    int read_pos, read_dt; char read_char;
    inline int read (int &p = read_pos){
        p = 0, read_dt = 1; read_char = getchar ();
        while (! isdigit (read_char)){
            if (read_char == '-')
                read_dt = - 1;
            read_char = getchar ();
        }
        while (isdigit (read_char)){
            p = (p << 1) + (p << 3) + read_char - 48;
            read_char = getchar ();
        }
        return p = p * read_dt;
    }
    int write_sta[65], write_top;
    inline void write (int x){
        if (x < 0)
            putchar ('-'), x = - x;
        write_top = 0;
        do
            write_sta[write_top ++] = x % 10, x /= 10;
        while (x);
        while (write_top)
            putchar (write_sta[-- write_top] + 48);
    }
}

const int N = 500, mod = 998244353;
int n, m, c[N + 5][N + 5], pwm[N * N + 5], pwt[N * N + 5];
int jc[N + 5], inv[N + 5], inj[N + 5];

inline int power (int a, int p){
    static int res; res = 1;
    while (p > 0){
        if (p & 1) res = res * a % mod;
        a = a * a % mod;
        p >>= 1;
    }
    return res;
}
inline int invn (int p){ return power (p, mod - 2); }
inline int C (int a, int b){ if (a < b) return 0; return jc[a] * inj[b] % mod * inj[a - b] % mod; }
inline int C2 (int a){ return a * (a - 1) / 2; }

signed main (){
    STCLOCK

    inv[1] = jc[0] = jc[1] = inj[0] = inj[1] = 1;
    for (int i = 2;i <= N;++ i){
        inv[i] = inv[i - mod % i] * (mod / i + 1) % mod;
        inj[i] = inj[i - 1] * inv[i] % mod;
        jc[i] = jc[i - 1] * i % mod;
    }
    io::read (n), io::read (m);
    pwm[0] = 1;
    for (int i = 1;i <= N * N;++ i) pwm[i] = pwm[i - 1] * m % mod;
    for (int i = 0;i <= n;++ i) c[0][i] = 1;
    for (int i = 1;i <= m;++ i){
        pwt[0] = 1;
        for (int j = 1;j <= N * N;++ j)
            pwt[j] = pwt[j - 1] * (m - i) % mod;
        c[i][0] = c[i][1] = 1;
        for (int j = 2;j <= n;++ j){
            c[i][j] = pwm[C2 (j)];
            for (int k = 1;k < j;++ k)
                c[i][j] -= pwm[C2 (j - k)] * C (j - 1, k - 1) % mod * c[i][k] % mod * pwt[k * (j - k)] % mod;
            c[i][j] = (c[i][j] % mod + mod) % mod;
        }
    }

    int ans = m * (n - 1) * power (m, C2 (n)) % mod;
    for (int k = 1;k < m;++ k)
        for (int i = 1;i <= n;++ i)
            ans = (ans - C (n, i) * c[k][i] % mod * power (m - k, i * (n - i)) % mod * power (m, C2 (n - i)) % mod * (i - 1) % mod) % mod;
    io::write ((ans + mod) % mod), putchar ('\n');

    TIMENOW
    return 0;
}

提出情報

ジャッジ結果