C++ 解法, 执行用时: 78ms, 内存消耗: 28024K, 提交时间: 2021-05-27 15:50:37

#include<cstdio>
#include<iostream>
using namespace std;
int f[3005], g[3005], com[3005][3005];
int getmod(long long x, int mod){return x >= mod ? x % mod : x;}
int qp(int a, int x, int mod){
	int i = 1;
	for(;x;x >>= 1, a = getmod(1ll * a * a, mod))if(x & 1)i = getmod(1ll * i * a, mod);
	return i;
}
inline void solve(int n, int m, int mod){
	int i, j, k;
	if(n == 1)for(i = 0;i <= m;i++)f[i] = 1;
	else{
		solve(n >> 1, m, mod);
		j = qp(m * (m - 3) + 3, n / 2, mod);
		for(i = 0;i <= m;i++){
			g[i] = getmod((1ll + j) * f[i], mod);
			for(k = 0;k < i;k++){
				g[i] += 1ll * j * com[i][k] % mod * f[k] % mod * qp(n >> 1, i - k, mod) % mod;
				if(g[i] >= mod)g[i] -= mod;
			}
		}swap(f, g);
		if(n & 1)for(i = 0, j = qp(m * (m - 3) + 3, n - 1, mod);i <= m;i++){
			f[i] += getmod(1ll * j * qp(n, i, mod), mod);
			if(f[i] >= mod)f[i] -= mod;
		}
	}
}
inline int solve2(int n, int x, int mod){
	if(n <= 0)return 0;
	int r = (1ll + qp(x, n >> 1, mod)) * solve2(n >> 1, x, mod) % mod;
	if(n & 1){
		r += qp(x, n, mod);
		if(r >= mod)r -= mod;
	}return r;
}
int main(){
	int n, m, i, j, mod;
	scanf("%d%d%d", &n, &m, &mod);
	for(i = 0;i <= m;i++)
		for(j = com[i][0] = 1;j <= i;j++)
			com[i][j] = (com[i - 1][j] + com[i - 1][j - 1]) % mod;
	if(m == 1)printf("0");
	else if(mod > 3000){
		solve(n, m, mod);
		i = 1ll * f[m] * qp(2, m, mod) % mod * m % mod * (m - 1) % mod;
		printf("%d", i);
	}else{
		int x = m * (m - 3) + 3, s = n >= mod ? 1 + solve2(n / mod - 1, qp(x, mod, mod), mod) : 0;
		for(i = 1, j = 0;i < mod;i++){
			j += 1ll * qp(i, m, mod) * qp(x, i - 1, mod) % mod;
			if(j >= mod)j -= mod;
		}j = 1ll * j * s % mod;
		for(i = n % mod, s = 0;i;i--){
			s += 1ll * qp(i, m, mod) * qp(x, i - 1, mod) % mod;
			if(s >= mod)s -= mod;
		}s = 1ll * s * qp(x, n / mod * mod, mod) % mod;
		j += s;
		if(j >= mod)j -= mod;
		j = 1ll * j * qp(2, m, mod) % mod * m % mod * (m - 1) % mod;
		printf("%d", j);
	}return 0;
}