【2020全国统一省选】组合数问题 题解

题目大意

  求

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

  其中 $n,x,p$ 为给定整数，$f(k)$ 为给定多项式 $f(k)=\sum_{i=0}^m a_ik^i$ 。

  $n,x,p,a_i \le 10^9,\ \ m \le \min(n,1000)$
  1s

$$\\$$ $$\\$$ $$\\$$

题解

  转了一圈，这题的推法似乎多种多样啊。。。（虽然本质相同
  就记录一个我觉得比较好的吧。

  核心思路就是 $k^i\binom{n}{k}$ 写成下降幂多项式，然后发现有奇效。

  设 $f(k)=\sum_{i=0}^m a_ik^i$ 转化成下降幂多项式为

$$f(k)=\sum_{i=0}^m b_i k^{\underline i} = \sum_{i=0}^m b_i \frac{k!}{(k-i)!}$$

  代入原式有

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

  这个东西 $O(m)$ 循环一遍就好了，$(x+1)^{n-i}$ 可以预处理也可以快速幂。

  至于 $b_i$ 的求法，也就是多项式转下降幂多项式，根据

$$x^i = \sum_{j=0}^i S(i,j) x^{\underline j}$$

  （其中 $S(i,j)$ 表示第二类斯特林数）可得

$$\begin{aligned} \sum_{i=0}^m a_ix^i &= \sum_{i=0}^m a_i \sum_{j=0}^i S(i,j) x^{\underline j} \\ &= \sum_{j=0} x^{\underline j} \sum_{i=j}^m a_i S(i,j) \end{aligned}$$

  因此预处理第二类斯特林数，然后 $b_j= \sum_{i=j}^m a_iS(i,j)$ 即可。

代码

#include<bits/stdc++.h>
#define fo(i,a,b) for(int i=a;i<=b;i++)
using namespace std;

typedef long long LL;

const int maxm=1005;

LL n,x,mo,a[maxm];
int m;

LL S[maxm][maxm];
void S_pre(int n)
{
	fo(i,0,m)
	{
		fo(j,1,i-1) S[i][j]=(S[i-1][j-1]+j*S[i-1][j])%mo;
		S[i][i]=1;
	}
}

LL b[maxm];
void FFP()
{
	fo(i,0,m)
		fo(j,i,m) (b[i]+=a[j]*S[j][i])%=mo;
}

LL Pow(LL x,LL y)
{
	LL re=1;
	for(; y; y>>=1, x=x*x%mo) if (y&1) re=re*x%mo;
	return re;
}

int main()
{
	freopen("problem.in","r",stdin);
	freopen("problem.out","w",stdout);
	
	scanf("%lld %lld %lld %d",&n,&x,&mo,&m);
	fo(i,0,m) scanf("%lld",&a[i]);
	
	S_pre(m);
	FFP();
	
	LL ndown=1, xpow=1, ans=0;
	fo(i,0,m)
	{
		(ans+=b[i]*xpow%mo*ndown%mo*Pow(x+1,n-i))%=mo;
		(xpow*=x)%=mo;
		(ndown*=n-i)%=mo;
	}
	
	printf("%lld\n",ans);
}