P6620 [省选联考 2020 A 卷] 组合数问题

众所周知，小葱同学擅长计算，尤其擅长计算组合数。小葱现在希望你计算

$$\left(\sum_{k=0}^{n}f(k)\times x^k\times \binom{n}{k}\right)\bmod p$$

的值。其中 $n$, $x$, $p$ 为给定的整数，$f(k)$ 为给定的一个 $m$ 次多项式 $f(k) = a_0 + a_1k + a_2k^2 + \cdots + a_mk^m$。$\binom{n}{k}$ 为组合数，其值为 $\binom{n}{k} = \frac{n!}{k!(n-k)!}$。

分析

下降幂能解决很多与组合数有关的问题，看到多项式/幂，先冲上去用斯特林数转下降幂多项式。

$$f(k)=\sum_{i=0}^{m}a_i k^i$$

把 $k^i$ 用第二类斯特林数变成 $\sum_{j=0}^i{i \brace j}k^{\underline j}$ 的形式。

$$\sum_{i=0}^m a_i\sum_{j=0}^i{i \brace j}k^{\underline j}$$

交换枚举顺序：

$$\sum_{i=0}^m k^{\underline i}\sum_{j=i}^m{j \brace i}a_j$$

设 $b_i$ 的 $\sum_{j=i}^m{j \brace i}a_j$，则 $f(k)$ 等于：

$$\sum_{i=0}^m b_i k^{\underline i}$$

带入原式，得：

$$\sum_{k=0}^{n}\sum_{i=0}^m b_i k^{\underline i} x^k \binom{n}{k}$$

把下降幂和组合数相乘：

$$\sum_{k=0}^{n}\sum_{i=0}^m b_i x^k n^{\underline i} \binom{n-i}{k-i} \\$$

交换枚举顺序：

$$\sum_{i=0}^{m}b_i n^{\underline i}\sum_{k=0}^n x^k \binom{n-i}{k-i} \\$$

设 $k'=k-i$，原式化为：

$$\sum_{i=0}^{m}b_i n^{\underline i}\sum_{k'=0}^n x^{k'+i} \binom{n-i}{k'} \\ \sum_{i=0}^{m}b_i n^{\underline i} x^i\sum_{k'=0}^n x^{k'} \binom{n-i}{k'} \\$$

$n>n-i$ 没有意义，使用二项式定理：

$$\sum_{i=0}^{m}b_i n^{\underline i} x^i\sum_{k'=0}^{n-i} x^{k'} \binom{n-i}{k'} \\ \sum_{i=0}^{m}b_i n^{\underline i} x^i(x+1)^{n-i} \\$$

$b_i$ 可以在 $O(m^2)$ 的时间复杂度内预处理出，总时间复杂度 $O(m^2)$。

代码：

#include <bits/stdc++.h>

using namespace std;

#define int long long

inline int read() {
    int x = 0, f = 1; char ch = getchar();
    for (; !isdigit(ch); ch = getchar()) f -= (ch == '-') * 2;
    for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);
    return x * f;
}

const int N = 2010;

int n, m, x, mod;
int fact[N], a[N], b[N], g[N], s[N][N], facinv[N];

int qpow(int a, int b) {
    int res = 1 % mod;
    for (; b; b >>= 1) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
    }
    return res;
}

signed main() {
    n = read(), x = read(), mod = read(); m = read();
    fact[0] = facinv[0] = 1;
    for (int i = 1; i <= m; i ++ ) fact[i] = fact[i - 1] * i % mod;
    facinv[m] = qpow(fact[m], mod - 2);
    for (int i = m - 1; i >= 1; i -- ) facinv[i] = facinv[i + 1] * (i + 1) % mod;
    for (int i = 0; i <= m; i ++ ) a[i] = read();
    if (m == 0) printf("%lld\n", a[0] * qpow(x + 1, n) % mod);
    else {
        int ans = 0;
        s[0][0] = 1;
        for (int i = 1; i <= m; i ++ ) {
            for (int j = 1; j <= i; j ++ ) {
                s[i][j] = (s[i - 1][j - 1] + s[i - 1][j] * j) % mod;
            }
        }
        for (int i = 0; i <= m; i ++ ) {
            for (int j = i; j <= m; j ++ ) {
                b[i] = (b[i] + a[j] % mod * s[j][i] % mod) % mod;
            }
        }
        g[0] = 1;
        for (int i = 1; i <= m; i ++ ) g[i] = g[i - 1] * (n - i + 1) % mod;
        for (int i = 0; i <= m; i ++ ) {
            int res = g[i] * b[i] % mod * qpow(x, i) % mod * qpow(x + 1, n - i) % mod;
            ans = (ans + res) % mod;
        }
        printf("%lld\n", ans);
    }
    return 0;
}

P4827 [国家集训队] Crash 的文明世界

Crash 小朋友最近迷上了一款游戏——文明5 (Civilization V)。在这个游戏中，玩家可以建立和发展自己的国家，通过外交和别的国家交流，或是通过战争征服别的国家。

现在 Crash 已经拥有了一个 $n$ 个城市的国家，这些城市之间通过道路相连。由于建设道路是有花费的，因此 Crash 只修建了 $n-1$ 条道路连接这些城市，不过可以保证任意两个城市都有路径相通。

在游戏中，Crash 需要选择一个城市作为他的国家的首都，选择首都需要考虑很多指标，有一个指标是这样的：

$$S(i) = \sum_{j = 1}^{n}{\rm dist}(i, j) ^ k$$

其中 $S(i)$ 表示第 $i$ 个城市的指标值，${\rm dist}(i, j)$ 表示第 $i$ 个城市到第 $j$ 个城市需要经过的道路条数的最小值，$k$ 为一个常数且为正整数。

因此 Crash 交给你一个简单的任务：给出城市之间的道路，对于每个城市，输出这个城市的指标值，由于指标值可能会很大，所以你只需要输出这个数 $\bmod\ 10007$ 的值。

分析

$$S(i) = \sum_{j = 1}^{n}{\rm dist}(i, j) ^ k \\ S(i) = \sum_{j = 1}^{n}\sum_{l=0}^k{k \brace l}{\rm dist}(i, j)^{\underline l}$$

交换枚举顺序：

$$S(i) = \sum_{l = 0}^{k}{k \brace l}\sum_{j=1}^n{\rm dist}(i, j)^{\underline l}$$