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

都说和UOJ #269. 【清华集训2016】如何优雅地求和很像,但是做过那题的我还是想不到转成下降幂,真是白学了啊

假设我们现在把多项式(f(k)=sum_{i=0}^ m a_ik^i)转化为(f(k)=sum_{i=0}^m b_ik^{underline{i}}),运用下降幂与组合数相乘的漂亮性质:

[C_n^k imes k^{underline{m}}=C_{n-m}^{k-m} imes n^{underline{m}} ]

证明很简单,两边全部拆开乘一乘就发现是相等的,因此我们推一下式子:

[sum_{k=0}^n f(k) imes x^k imes C_n^k\ =sum_{i=0}^mb_i n^{underline{i}}sum_{k=0}^n C_{n-i}^{k-i} x^k\ =sum_{i=0}^mb_i n^{underline{i}}sum_{k=0}^{n-i} C_{n-i}^{k} x^{k+i}\ =sum_{i=0}^mb_i n^{underline{i}}x^isum_{k=0}^{n-i} C_{n-i}^{k} x^{k}\ =sum_{i=0}^mb_i n^{underline{i}}x^i(x+1)^{n-i} ]

考虑如何快速把一个多项式转成下降幂形式,套用经典的第二类斯特林数性质:

[x^n=sum_{i=0}^n left{^n_i ight} x^{underline{i}} ]

带入得:

[f(k)=sum_{i=0}^ m a_ik^i=sum_{i=0}^ m a_i sum_{j=0}^i left{^i_j ight} k^{underline{j}}\ =sum_{i=0}^m k^{underline{i}}sum_{j=i}^m left{^j_i ight} a_j ]

因此(b_i=sum_{j=i}^m left{^j_i ight} a_j),直接(O(m^2))预处理便可直接(O(m))计算答案

#include<cstdio>
#define RI register int
#define CI const int&
using namespace std;
const int N=1005;
int n,x,mod,m,a[N],b[N],s[N][N],ans;
inline int quick_pow(int x,int p=mod-2,int mul=1)
{
	for (;p;p>>=1,x=1LL*x*x%mod) if (p&1) mul=1LL*mul*x%mod; return mul;
}
int main()
{
	RI i,j; for (scanf("%d%d%d%d",&n,&x,&mod,&m),i=0;i<=m;++i)
	scanf("%d",&a[i]); for (s[0][0]=s[1][1]=1,i=2;i<=m;++i) for (j=1;j<=i;++j)
	s[i][j]=(s[i-1][j-1]+1LL*s[i-1][j]*j%mod)%mod;
	for (i=0;i<=m;++i) for (j=i;j<=m;++j) (b[i]+=1LL*s[j][i]*a[j]%mod)%=mod;
	int cur=1; for (i=0;i<=m;++i)
	(ans+=1LL*b[i]*cur%mod*quick_pow(x,i)%mod*quick_pow(x+1,n-i)%mod)%=mod,cur=1LL*cur*(n-i)%mod;
	return printf("%d",ans),0;
}
原文地址:https://www.cnblogs.com/cjjsb/p/13397896.html