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

StranGePants / 2023-05-13 / 原文

组合数问题

首先明确下降幂即

\[k^{\underline m}=\sum_{i=k-m+1}^ki \]

不难发现有

\[\binom{n}{k}k^{\underline m}=\binom{n-m}{k-m}n^{\underline m} \]

我们尝试把普通幂多项式转为下降幂多项式

\[\sum_{i=0}^ma_i k^i=\sum_{i=0}^m b_i k^{\underline i} \]

由第二类斯特林数的性质我们有
$k^n=\sum_{i=0}^n$ $n \brace i $ $k^{\underline i}$
那么

$\sum_{i=0}^ma_i k^i$=$\sum_{i=0}^ma_i\sum_{j=0}^i$ $i \brace j$ $k^{\underline j}$
=$\sum_{j=0}^mk^{\underline j}$ $\sum_{i=j}^m$ $i \brace j$ $a_i$
那么我们就可以 $\Omicron(m^2)$ 求出 b
对于整个式子在用上面提到的结论代换即可(xiebuwanle

#include<cstdio>
#include<iostream>
using namespace std;
const int MAXN=1005;
#define ll long long
ll n,x,Mod,m,a[MAXN],b[MAXN],dp[MAXN][MAXN],tmp,va[MAXN],op,res,vv[MAXN];
void init(){
	dp[0][0]=1;
	for(int i=1;i<=m;i++){
		for(int j=1;j<=i;j++){
			dp[i][j]=(dp[i-1][j-1]+1LL*j*dp[i-1][j])%Mod;
		}
	}
}
ll ksm(ll a,ll b){
	ll res=1;
	while(b){
		if(b&1) res=res*a%Mod;a=a*a%Mod;b>>=1;
	}return res;
}
int main(){
	scanf("%lld%lld%lld%lld",&n,&x,&Mod,&m);op=1;init();vv[0]=1;
	for(int i=0;i<=m;i++){
		scanf("%lld",&a[i]);
		if(i>0) vv[i]=vv[i-1]*x%Mod;
	}
	for(int i=0;i<=m;i++){
		for(int j=i;j<=m;j++){
			b[i]=(b[i]+dp[j][i]*a[j]%Mod)%Mod;
		}
	}
	for(int i=0;i<=m;i++){
		res=(res+(op*b[i]%Mod*vv[i]%Mod*ksm(x+1,n-i)%Mod))%Mod;op=op*(n-i)%Mod;
	}
	printf("%lld",res);
}/*
g++ 111.cpp -o 111
./111
*/