P4463 [集训队互测 2012] calc 题解

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;
}