代码

#include <algorithm>
#include <iostream>
#include <cstdio>
using namespace std;

#define il inline
#define re register
#define ll long long
#define rep(i, s, t) for(int i = s; i <= t; i++)
#define per(i, t, s) for(int i = t; i >= s; i--)

il ll rd() {
    re int x = 0, f = 1;
    re char ch = getchar();
    while(!isdigit(ch)) {if(ch == '-') f = -f; ch = getchar();}
    while(isdigit(ch)) {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
template <typename T> void chkmin (T & a, T const& b)  {if(a > b) a = b;} 
template <typename T> void chkmax (T & a, T const& b)  {if(a < b) a = b;}

const int N = 5010, P = 1004535809;
int S[N][N], n, m, K;

il int pw(int a, int b) {
    int res = 1;
    while(b) {
        if(b & 1) res = (ll)res * (ll)a % P;
        a = (ll)a * (ll)a % P;
        b >>= 1;
    }
    return res;
}
il int add(const int &x, const int & y) {return x + y >= P ? x + y - P : x + y;}
il int rds(const int &x, const int & y) {return x - y < 0 ? x - y + P : x - y;}
int S1[N][N], f[N];

il int F(int x) { //C(K ^ x, n) * n! = (K ^ x) ^ {_n_}
    int res = 1, kx = pw(K, x);
    rep(i, 1, n) {
        res = (ll)res * kx % P;
        kx = rds(kx, 1);
    }
    return res;
}

il void init() {
    const int nn = N - 10;
    S1[0][0] = 1;
    rep(i, 1, nn) rep(j, 1, i)
        S1[i][j] = add(S1[i - 1][j - 1], (ll)S1[i - 1][j] * (ll)(i - 1) % P);
}

il void solve() {
    n = rd(), m = rd(), K = rd();
    rep(i, 0, m) f[i] = F(i);
    int sg = (m & 1) ? -1 : 1;
    int ans = 0;
    rep(i, 0, m) {
        if(sg > 0) ans = add(ans, (ll)S1[m][i] * f[i] % P);
        else ans = rds(ans, (ll)S1[m][i] * f[i] % P);
        sg = -sg;
    }
    printf("%d\n", ans);
}

signed main() {
    //freopen("square.in", "r", stdin);
    //freopen("square.out", "w", stdout);
    init();
    int T = rd(); while(T--) solve();
    return 0;
}

评测结果