[洛谷 6620,loj 3300][联合省选 2020 A]组合数问题

题目链接

https://www.luogu.com.cn/problem/P6620

https://loj.ac/problem/3300

题解

本题要求我们求出:

$$
\sum_{k=0}^{n}f(k)\times x^k\times C_n^k
$$

其中 \(f(k)\) 为一个次数为 \(m\) 的普通多项式 \(\sum_{i=0}^m a_ix^i\)。

在介绍解法之前,我们先给出若干定义和引理(熟悉的同学可直接跳过这些内容):

定义 1:定义 \(x\) 的 \(k\) 次下降幂 \(x^{\underline{k}}=\frac{x!}{(x-k)!}\),这也被称为一个关于 \(x\) 的下降幂单项式

定义 2:定义下降幂多项式为有限多下降幂单项式的和,形如 \(\sum_{i=0}^k a_ix^{\underline{i}}\)。与之相对应的是,形如 \(\sum_{i=0}^k a_ix^i\) 的多项式,我们称为普通多项式

定义 3:我们定义第二类斯特林数 \(\begin{Bmatrix}n\\m\end{Bmatrix}\) 为将 \(n\) 个完全相同的元素,不重不漏地划分成 \(m\) 个集合的方案数。

说完了定义,我们接下来给出若干引理和定理:

定理 0(二项式定理):\((x+y)^k=\sum_{i=0}^k C_k^i x^iy^{k-i}\)。

考虑组合意义即可得证。

定理 1.1:\(m \times C_n^m=n \times C_{n-1}^{m-1}\)。

高中学过组合数学的同学可能都熟悉这个性质。只需将两边的组合数全部展开为阶乘形式即可得证。

事实上上面这个定理可以进一步推广到下降幂的情形(也就是下面的 定理 1.2):

定理 1.2:\(m^{\underline{k}} \times C_{n}^{m}=n^{\underline{k}} \times C_{n-k}^{m-k}\)。

证明仍然是直接展开等式两边,这里略去。

引理 1:\(x^k=\sum_{i=0}^k \begin{Bmatrix}k\\i\end{Bmatrix} x^{\underline{i}}\)。

证明从略。

利用这个引理,我们可以给出普通多项式转化为下降幂多项式的方法(也就是下面的 定理 2):

定理 2:记普通多项式 \(f(x)=\sum_{i=0}^k a_ix^{i}\),下降幂多项式 \(g(x)=\sum_{i=0}^k b_ix^{\underline{i}}\),且 \(f(x)=g(x)\),则有 \(b_i=\sum_{j=i}^k \begin{Bmatrix}j\\i\end{Bmatrix}a_j\)。

证明考虑根据 引理 1 将普通多项式展开:

$$
\begin{aligned}
\sum_{i=0}^k a_ix^i &= \sum_{i=0}^k a_i \sum_{j=0}^i \begin{Bmatrix}i\\j\end{Bmatrix} x^{\underline{j}}\\
&= \sum_{i=0}^k x^{\underline{i}}\sum_{j=i}^k \begin{Bmatrix}j\\i\end{Bmatrix} a_j
\end{aligned}
$$

定理 3(第二类斯特林数递推公式):\(\begin{Bmatrix}n\\m\end{Bmatrix}=m\times \begin{Bmatrix}n-1\\m\end{Bmatrix}+\begin{Bmatrix}n-1\\m-1\end{Bmatrix}\)

还是考虑组合意义:对于每个新增的元素,我们可以将其放在原有的集合中,或者是单独安排一个集合。

利用该定理,我们可以在 \(O(n^2)\) 时间内递推出我们需要的第二类斯特林数的值。

接下来进入正题。

我们发现一个普通多项式与组合数相乘并没有什么显然的性质,而定理 1.2 则告诉了我们下降幂多项式与组合数相乘的性质。因此考虑根据 定理 2,将普通多项式 \(f(x)=\sum_{i=0}^k a_ix^{i}\) 转化为下降幂多项式 \(g(x)=\sum_{i=0}^k b_ix^{\underline{i}}\)。

也就是说我们所求变成了:

$$
\sum_{k=0}^{n}g(k)\times x^k\times C_n^k
$$

现在利用 定理 1.2 改写上式:

$$
\begin{aligned}
\sum_{k=0}^{n}g(k)\times x^k\times C_n^k &= \sum_{k=0}^{n}\sum_{i=0}^m b_i \times k^{\underline{i}}\times x^k\times C_n^k\\
&= \sum_{k=0}^{n}x^k\sum_{i=0}^m b_i \times n^{\underline{i}} \times C_{n-i}^{k-i}\\
&= \sum_{i=0}^{m}b_i \times n^{\underline{i}} \sum_{k=0}^n C_{n-i}^{k-i} x^k\\
\end{aligned}
$$

注意到只有 \(k-i \geq 0\) 的时候才会对答案产生贡献,考虑枚举 \(k-i\) 的值,为了避免混淆,令 \(k’=k-i\):

$$
\begin{aligned}
\sum_{i=0}^{m}b_i \times n^{\underline{i}} \sum_{k’=0}^{n-i} C_{n-i}^{k’} x^{k’+i} &= \sum_{i=0}^{m}b_i \times n^{\underline{i}} \times x^i \sum_{k’=0}^{n-i} C_{n-i}^{k’} x^{k’}\\
&= \sum_{i=0}^{m}b_i \times n^{\underline{i}} \times x^i \times (x+1)^{n-i}
\end{aligned}
$$

最后一步推导实际上就是二项式定理的逆用。

到这里本题就做完了。

上式可以 \(O(m)\) 来计算,而本题时间瓶颈主要在递推求第二类斯特林数上,这部分的时间复杂度为 \(O(m^2)\)。

// Problem : P6620 [省选联考 2020 A 卷] 组合数问题
// Contest : Luogu
// URL : https://www.luogu.com.cn/problem/P6620
// Memory Limit : 512 MB
// Time Limit : 1000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#include <iostream>
using namespace std;
int n,x,p,m;
long long a[1005],b[1005];
long long s[1005][1005];
long long f[1005],g[1005],h[1005];
long long fpow(long long x,long long y)
{
 long long ans=1;
 while(y)
 {
  if(y&1)ans=ans*x%p;
  x=x*x%p;
  y>>=1;
 }
 return ans;
}
int main()
{
 cin>>n>>x>>p>>m;
 for(int i=0;i<=m;i++)
  cin>>a[i];
 s[0][0]=1;
 for(int i=1;i<=m;i++)
  for(int j=1;j<=i;j++)
   s[i][j]=(j*s[i-1][j]+s[i-1][j-1])%p;
 for(int i=0;i<=m;i++)
  for(int j=i;j<=m;j++)
   b[i]=(b[i]+s[j][i]*a[j])%p;
 f[0]=1,g[0]=1,h[m]=fpow(x+1,n-m);
 for(int i=1;i<=m;i++)
 {
  f[i]=f[i-1]*(n-i+1)%p;
  g[i]=g[i-1]*x%p;
 }
 for(int i=m-1;i>=0;i--)
  h[i]=h[i+1]*(x+1)%p;
 long long ans=0;
 for(int i=0;i<=m;i++)
  ans=(ans+b[i]*f[i]%p*g[i]%p*h[i])%p;
 cout<<ans<<endl;
 return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据