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

ix35 · 2020-06-23 16:36:41 · 题解

之前不会一些斯特林数和下降幂多项式的知识，考场上现推了很多东西，出发点基本只用到了如下组合恒等式：

k\times \binom n k=n\times \binom {n-1}{k-1}

以及二项式定理：

(1+x)^n=\sum\limits_{i=0}^n\binom n i x^i

在这里和大家分享一下如果不会任何特殊的奇技淫巧，该怎么推出各种所需结论&做出本题，也还原了一下考场的思维过程。

首先题目中的多项式 f(k) 显然可以拆成 m+1 个单项式之和，我们只讨论单项式的结果，即：

\sum\limits_{k=1}^n k^p\times x^k\times \binom n k

首先我们看到了 k^p\times \binom n k，就想到了最上面的那个组合恒等式，我们尝试将它扩展到 k 的更高次幂的形式：

k\times \binom n k=n\times \binom{n-1}{k-1}

k^2\times \binom n k=k\times\Big(n\times \binom {n-1}{k-1}\Big)

=(k-1)\times n\times \binom {n-1}{k-1}+n\times \binom {n-1}{k-1}

=n\times (n-1)\times \binom {n-2}{k-2}+n\times \binom{n-1}{k-1}

好像还不能看出很多规律，我们再推一个 p=3：

k^3\times \binom n k =k\times \Big(n\times (n-1)\times \binom {n-2}{k-2}+n\times \binom {n-1}{k-1}\Big)

=n(n-1)(n-2)\binom{n-3}{k-3}+2n(n-1)\binom{n-2}{k-2}+n(n-1)\binom{n-2}{k-2}+n\binom{n-1}{k-1}

=n(n-1)(n-2)\binom{n-3}{k-3}+3n(n-1)\binom{n-2}{k-2}+n\binom{n-1}{k-1}

于是我们发现，似乎 k^p\times \binom n k 可以拆成很多形如 n(n-1)\ldots (n-l+1)\times \binom {n-l}{k-l} 的式子的和。

而前面这个东西就是所谓的下降幂了，我们记为 n^{\underline l}。

我们可以得到：

k^p\times \binom n k=\sum\limits_{i=1}^p S(p,i)\times n^{\underline i}\times \binom {n-i}{k-i}

其中 S(p,i) 是待定的系数，但是根据上面的计算过程，我们可以得到关于 S(p,i) 的恒等式：

S(p,i)=i\times S(p-1,i)+S(p-1,i-1)

前面的 i\times S(p-1,i) 表示从 k^{p-1}\times \binom n k 中继承过来的 n^{\underline i}\times \binom {n-i}{k-i} 项（我们将 k 拆成 k-i+i 中后面的 +i 就在这里体现），后面的 S(p-1,i-1) 表示原先的下一项，在乘上一个 k-i 之后变成了 i 这一项的系数。

这个系数实际上就是第二类斯特林数，不过知不知道都不影响，有这个递推式就够了。

接下来推原来的式子：

\sum\limits_{k=1}^n k^p\times x^k\times \binom n k=\sum\limits_{j=1}^p S(p,j)\times n^{\underline j}\times \Big(\sum\limits_{k=j}^n x^k\times \binom {n-j}{k-j}\Big)

这一步只是套用了上面的结论，接下来大括号里面的式子用二项式定理打开：

\sum\limits_{k=j}^nx^k\times \binom {n-j}{k-j}=x^j\times\sum\limits_{k=0}^{n-j}\binom {n-j}{k}x^k=x^j\times (1+x)^{n-j}

这样里面的式子就做完了，再把原来的多项式 f(k) 放进来：

Ans=a_0(1+x)^n+\sum\limits_{i=1}^m a_i\times \Big(\sum\limits_{j=1}^i S(i,j)\times n^{\underline j}\times x^j\times (1+x)^{n-j}\Big)

注意前面 a_0 要特殊处理，因为 p=0 时上面我们推出来的式子不成立（是以 1 为起始条件的）。

这样已经可以在 O(m^2\log m) 的时间中计算了，想要得到 O(m^2) 做法也很容易，交换一下求和号即可：

Ans=a_0(1+x)^n+\sum\limits_{j=1}^m n^{\underline j}\times x^j\times (1+x)^{n-j}\times \Big(\sum\limits_{i=j}^m a_i\times S(i,j)\Big)

#include <bits/stdc++.h>
using namespace std;
const int MAXN=1010;
int n,x,p,m,ans,a[MAXN],trans[MAXN][MAXN];
int qpow (int a,int b) {
    int res=1;
    while (b) {
        if (b&1) {res=(1ll*res*a)%p;}
        a=(1ll*a*a)%p,b>>=1;
    }
    return res;
}
int main () {
    freopen("problem.in","r",stdin);
    freopen("problem.out","w",stdout);
    scanf("%d%d%d%d",&n,&x,&p,&m);
    for (int i=0;i<=m;i++) {
        scanf("%d",&a[i]);
    }
    trans[1][1]=1;
    for (int i=2;i<=m;i++) {
        for (int j=1;j<=i;j++) {
            trans[i][j]=((1ll*trans[i-1][j]*j)%p+trans[i-1][j-1])%p;
        }
    }
    ans=(1ll*a[0]*qpow((x+1)%p,n))%p;
    for (int i=1;i<=m;i++) {
        int tmp=(1ll*qpow(x%p,i)*qpow((x+1)%p,n-i))%p,val=0;
        for (int j=0;j<=i-1;j++) {tmp=(1ll*tmp*(n-j))%p;}
        for (int j=i;j<=m;j++) {
            val=(val+(1ll*trans[j][i]*a[j])%p)%p;
        }
        ans=(ans+(1ll*val*tmp)%p)%p;
    }
    printf("%d\n",ans);
    return 0;
}