省选真题选做

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

本题难点为下降幂的使用。

我们定义 \(n^{\underline{m}} = \prod\limits_{i=n-m+1}^{n} i\)，其在组合数计算中具有重要的作用。下降幂的性质：\(a^{\underline{b}}=a^{\underline{c}} \times (a-c)^{\underline{b-c}}\)。

同时我们定义下降幂多项式 \(g(k) = \prod\limits_{i=0}^{m} b_i k^{\underline{i}}\)，考虑原多项式 \(f(k) = \prod\limits_{i=0}^{m} b_i k^i\)，我们声称这两者之间可以进行转化，即普通多项式可以转成下降幂多项式，反之亦然。

考虑对于每个 \(b_i\) 计算结果，得到答案：

\[\sum\limits_{i=0}^{m} \sum\limits_{k=0}^{n} b_i k^{\underline{i}} \times x^k \times \dbinom{n}{k} \]

注意到 \(k^{\underline{i}} \times \dbinom{n}{k} = \dfrac{n^{\underline{k}} \times k^{\underline{i}}}{k^{\underline{k}}} = \dfrac{n^{\underline{k}}}{(k-i)^{\underline{k-i}}} = \dfrac{n^{\underline{i}} \times (n-i)^{\underline{k-i}}}{(k-i)^{\underline{k-i}}} = n^{\underline{i}} \times \dbinom{n-i}{k-i}\)。也就是说原式可以化为：

\[\sum\limits_{i=0}^{m} \sum\limits_{k=0}^{n} b_i \times x^k \times n^{\underline{i}} \times \dbinom{n-i}{k-i} \]

将一些常数项提出，得到：

\[\sum\limits_{i=0}^{m} b_i \times n^{\underline{i}} \times \sum\limits_{k=0}^{n} x^k \times \dbinom{n-i}{k-i} \]

显然，只有 \(k - i \geq 0\) 时组合数才能 \(> 0\)，故我们枚举 \(l = k - i\)，得：

\[\sum\limits_{i=0}^{m} b_i \times n^{\underline{i}} \times \sum\limits_{l=0}^{n-i} x^{l+i} \times \dbinom{n-i}{l} \]

继续化简：

\[\sum\limits_{i=0}^{m} b_i \times n^{\underline{i}} \times x^i \times \sum\limits_{l=0}^{n-i} x^{l} \times \dbinom{n-i}{l} \]

化简里面，发现本质上等于 \(\sum\limits_{l=0}^{n-i} \dbinom{n-i}{l} \times x^{l} \times 1^{n-i-l}\)，化简得到 \((x+1)^{n-i}\)，也就是说原式为：

\[\sum\limits_{i=0}^{m} b_i \times n^{\underline{i}} \times x^i \times (x+1)^{n-i} \]

于是问题落在了普通多项式转下降幂多项式上，这里我们引入第二类斯特林数 \(S(n,m)\) 表示将 \(n\) 个不同小球装进 \(k\) 个相同盒子，每个盒子非空的方案数。

根据定义，我们可以得知 \(S(0,0) = 1\)，\(S(n,m) = S(n-1,m-1) + m \times S(n-1,m)\)。同时根据斯特林数的定义，我们可以得到式子：

\[x^{n} = \sum\limits_{i=0}^{n} S(n,i) \times x^{\underline{i}} \]

于是本题可以在 \(O(m^2)\) 时间内完成多项式的转换，至此我们在 \(O(m^2)\) 内完成本题。

#include<iostream>
#include<cstdio>
using namespace std;
long long n,x,p;
int m;
long long S[1010][1010];
long long a[1010],b[1010];
long long pow_mod(long long num1,long long num2){long long num3=1;while(num2){if(num2&1){num3=num3*num1%p;}num1=num1*num1%p;num2>>=1;}return num3;
}
int main(){scanf("%lld %lld %lld %d",&n,&x,&p,&m);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%p)%p;}}for(int i=0;i<=m;i++){scanf("%lld",&a[i]);for(int j=0;j<=i;j++){b[j]+=a[i]*S[i][j]%p;b[j]%=p;}}long long ans=0,down_n=1;for(int i=0;i<=m;i++){ans+=b[i]*down_n%p*pow_mod(x,i)%p*pow_mod(x+1,n-i)%p;ans%=p;down_n=down_n*(n-i)%p;}printf("%lld",ans);return 0;
}