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

发布于 7 天前  32 次阅读


Link

一道题目=解锁inf知识点

前置知识

下降幂:

n^{\underline k} = \binom{n}{k}*k!

二项式定理

(x+y)^{n} = \sum_{k=0}^{n} \binom{n}{k} x^{x-k}y^{k}

并且我们注意到当y=1时,(x+1)^n = \sum_{k=0}^{n} \binom{n}{k} a^{n-k}

第二类斯特林数S(n,k) = S(n - 1,k-1) + k * S(n-1,k)

重要等式

\binom{n}{m} = \binom{n}{n - m}

x^k = \sum_{i=0}^{k} \binom{x}{i} * S(k,i) * i!

解释:x^k相当于把k个小球放进x个盒子里(允许空盒),那么方案就是枚举不空的盒子个数 × 小球放进去的方案数 × 盒子标号不同(不懂就私聊

Sol

解决完以上前置知识,我就花了小半小时(菜

看题目要我们解决的式子:

\sum_{k = 0}^{n} f(k)*x^k*\binom{n}{k}

f(k)是一个m次多项式,我们可以写成:

\sum_{k=0}^{n} \sum_{i=0}^{m} a_{i} * k^{i} * \binom{n}{k} * x^{k}

k^i用上面的恒等式替换

\sum_{k=0}^{n} \sum_{i=0}^{m} a_{i} * \sum_{p=0}^{i} S(i,p) * \binom{k}{p} * p! * \binom{n}{k} * x^k

观察到\binom{k}{p}\binom{n}{k}两项拆成阶乘形式:

\frac{k!}{p!(k-p)!} * \frac{n!}{k!(n-k)!}

同时消去k!,再同乘\frac{(n-p)!}{(n-p)!} = 1等式仍然成立:

\frac{n! (n-p)!}{p!(n-p)!(n-k)!(n-p)!} = \binom{n}{p}*\binom{n-p}{k-p}

所以此时式子变成了:

\sum_{k=0}^{n} \sum_{i=0}^{m} a_{i} * \sum_{p=0}^{i} S(i,p) * \binom{n}{p} * \binom{n-p}{k-p} * p! * x^k

我们将所有的求和限制提前,并且对每一项的顺序稍作改变:

\sum_{k=0}^{n} \sum_{i=0}^{m} \sum_{p=0}^{i} \binom{n-p}{n-k} * x^k * a_i * S(i,p) * p! * \binom{n}{p}

对二项式定理上面那个等式熟悉的话,我们感觉\binom{n-p}{n-k}x^k可以合并。我们需要将x的指数稍作修改

\sum_{k=0}^{n} \sum_{i=0}^{m} \sum_{p=0}^{i} \binom{n-p}{n-k} * x^{k-p} * x^p * a_i * S(i,p) * p! * \binom{n}{p}

此时可以合并

\sum_{i=0}^{m} \sum_{p=0}^{i} (x+1)^{n-p} * x^p * a_i * S(i,p) * p! * \binom{n}{p}

至此,(x+1)^{n-p}x^p两项均可通过快速幂计算,第二类斯特林数通过O(m^2)打表,p!\binom{n}{p}可以一起计算

没了

Code

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

#define int long long

const int SIZE = 1e3 + 5;

int n, x, p, m;
int a[SIZE], frac[SIZE], s[SIZE][SIZE];

inline int read()
{
    char ch = getchar();
    int f = 1, x = 0;
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + ch - '0'; ch = getchar(); }
    return x * f;
}

inline int qPow(int a, int b)
{
    int ans = 1;
    while (b) {
        if (b & 1) ans = ans * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return ans % p;
}

signed main()
{
    n = read(), x = read(), p = read(), m = read();
    for (int i = 0; i <= m; ++ i) a[i] = read();
    s[0][0] = 1;
    for (register int i = 1; i <= m; ++ i) {
        for (register int j = 1; j <= i; ++ j) 
            s[i][j] = (s[i - 1][j - 1] + 1ll * j * s[i - 1][j] % p) % p;
    }
    int ans = 0;
    for (register int i = 0; i <= m; ++ i) {
        frac[i] = qPow(x + 1, n - i);
        for (register int j = i - 1; j >= 0; -- j)
            frac[j] = frac[j + 1] * (x + 1) % p;
        for(register int j = 0, val1 = 1, val2 = 1; j <= i; ++ j, val1 = 1ll * val1 * (n - j + 1) % p, val2 = 1ll * val2 * x % p)
            ans = (ans + 1ll * a[i] * s[i][j] % p * val1 % p * val2 % p * frac[j] % p) % p;
    }
    printf("%lld\n", ans % p);
    return 0;
}

朴实沉毅