题解

由于题目保证了序列 $a$ 中每个元素互不相等，所以我们可以变序列为集合，最后将答案乘上 $n!$ 即可

考虑答案的生成函数，对于每个数 $i$ ，我显然有选和不选两种情况，选的话贡献就是 $ix$ ，不选的话贡献就是 $1$

所以

$$\begin{equation} \begin{split} ans &= n! \times [x^n] \prod_{i = 1}^m (1 + ix)\\ &= n! \times [x^n] exp(\sum_{i = 1}^m ln(1 + ix))\\ &= n! \times [x^n] exp(\sum_{i = 1}^m \sum_{j \ge 1} \frac{(-1) ^ {j + 1}}{j} (ix)^j)\\ &= n! \times [x^n] exp(\sum_{j \ge 1} \frac{(-1) ^ {j + 1}}{j} x^j \sum_{i = 1}^m i^j) \end{split} \end{equation} $$

设 $s(n) = \sum_{i = 0}^m i^n$ ，不难发现这是自然数幂和，用扰动法容易算出递推式为

$$s(n) = \frac{1}{n+1}((m + 1)^{n + 1} - \sum_{i = 0}^{n - 1} \binom{n + 1}{i} s(i)) $$

其中 $s(0) = \sum_{i = 0}^m i^0 = m + 1$，这里令 $0^0 = 1$

$O(n ^ 2)$ 暴力递推组合数， $O(n^2)$ 暴力递推自然数幂和， $O(n^2)$ 暴力递推多项式 exp，总复杂度为 $O(n^2)$

代码

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

const int N = 510;

LL n, m, p, mx, s[N], c[N][N], a[N], b[N];

LL ksm(LL v, LL tms)
{
    LL res = 1;
    for(; tms; tms >>= 1, v = v * v % p) if(tms & 1) res = res * v % p;
    return res;
}

void exp()
{
    b[0] = 1;
    for(int i = 1; i <= n; i++){
        for(int j = 0; j < i; j++)
            b[i] = (b[i] + (j + 1) * a[j + 1] % p * b[i - j - 1] % p) % p;
        b[i] = b[i] * ksm(i, p - 2) % p;
    }
}

int main()
{
    cin >> m >> n >> p, s[0] = m + 1, mx = n + 5;
    for(int i = 0; i <= mx; i++) c[i][0] = c[i][i] = 1;
    for(int i = 1; i <= mx; i++)
        for(int j = 1; j <= i; j++)
            c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % p;

    for(int i = 1; i <= n; i++){
        LL res = 0;
        for(int j = 0; j < i; j++)
            res = (res + c[i + 1][j] * s[j] % p) % p;
        s[i] = ksm(i + 1, p - 2) * (ksm(m + 1, i + 1) - res + p) % p;
        a[i] = ksm(i, p - 2) * ((i & 1) ? 1 : -1) * s[i];
        a[i] = (a[i] % p + p) % p;
    }
    exp();
    LL ans = b[n];
    for(int i = 2; i <= n; i++) ans = ans * i % p;
    cout << ans << endl;
    return 0;
}