Description
一个序列 \(a_1,a_2,\dots,a_n\) 是合法的，当且仅当：
- \(a_1,a_2,\dots,a_n\) 都是 \([1,k]\) 中的整数。
- \(a_1,a_2,\dots,a_n\) 互不相等。
一个序列的值定义为它里面所有数的乘积，即 \(a_1\times a_2\times\dots\times a_n\)。
求所有不同合法序列的值的和对 \(p\) 取模后的结果。两个序列不同当且仅当他们任意一位不同。
\(k \le 10 ^ 9\)，\(n \le 500\)，\(p \le 10 ^ 9\)，保证 \(p\) 为素数，保证 \(n + 1 < k < p\)。
Solution
先考虑一个暴力 dp。
设 \(f_{i,j}\) 表示前 \(i\) 个数，值域为 \([1,j]\) 且这些数单调递增的总和。
那么可以得到转移：\(f_{i,j}=f_{i,j-1}+j\times f_{i-1,j-1}\)。
时间复杂度：\(O(nk)\)。
考虑优化。
可以猜测 \(f_{i,j}\) 是关于 \(j\) 的某个多项式，且对于第一维相同的次数相同。
不妨设 \(g_i\) 表示 \(f_{i}\) 的系数。
那么把 \(f_i\) 做差分后的多项式系数为原来的系数 \(-1\)，即 \(f_{i,j}-f_{i,j-1}=j\times f_{i-1,j-1}\) 的系数为 \(g_i-1\)。
所以 \(g_i-1=g_{i-1}+1\)，也就是 \(g_i=g_{i-1}+2\)。
注意到 \(g_0\) 一定是 \(0\)，所以 \(g_i=2i\)。
然后只要求出 \(f_{n,1},f_{n,2},\dots,f_{n,2n+1}\)，然后做一遍拉格朗日插值即可。
时间复杂度：\(O(n^2)\)。
Code
#include <bits/stdc++.h>
#define int int64_t
const int kMaxN = 505;
int k, n, mod;
int f[kMaxN][kMaxN * 2];
int qpow(int bs, int idx = mod - 2) {
int ret = 1;
for (; idx; idx >>= 1, bs = 1ll * bs * bs % mod)
if (idx & 1)
ret = 1ll * ret * bs % mod;
return ret;
}
void dickdreamer() {
std::cin >> k >> n >> mod;
std::fill_n(f[0], std::min(2 * n + 1, k) + 1, 1);
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= std::min(2 * n + 1, k); ++j)
f[i][j] = (f[i][j - 1] + 1ll * j * f[i - 1][j - 1] % mod) % mod;
}
int ans = 0;
for (int i = 1; i <= 2 * n + 1; ++i) {
int tmpu = f[n][i], tmpd = 1;
for (int j = 1; j <= 2 * n + 1; ++j)
if (i != j)
tmpu = 1ll * tmpu * ((k - j + mod) % mod) % mod, tmpd = 1ll * tmpd * ((i - j + mod) % mod) % mod;
ans = (ans + 1ll * tmpu * qpow(tmpd) % mod) % mod;
}
for (int i = 1; i <= n; ++i)
ans = 1ll * ans * i % mod;
std::cout << ans << '\n';
}
int32_t main() {
#ifdef ORZXKR
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
int T = 1;
// std::cin >> T;
while (T--) dickdreamer();
// std::cerr << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
return 0;
}