记录编号	551759	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[统一省选 2020]组合数问题	最终得分	100
用户昵称	斯内普和骑士	是否通过	通过
代码语言	C++	运行时间	0.644 s
提交时间	2020-06-24 18:04:52	内存使用	23.07 MiB

#include<bits/stdc++.h>
using namespace std;
#define R register
typedef long long ll;
const int maxn=1110;
ll n,x,p,m,g_h_y;
ll fac[maxn],a[maxn],trans[maxn][maxn];
inline ll qpow(ll g,ll k,ll mod)
{
	ll res=1;
	while(k)
	{
		if(k&1)
		res=(res*g)%mod;
		if(k>>=1)
		g=g*g%mod;
	}
	return res;
}
inline void init(ll mod)
{
	fac[0]=1;
	for(R ll i=1;i<=1100;i++)
	fac[i]=fac[i-1]*i%mod;
	trans[1][1]=1;
	for (int i=2;i<=m;i++) 
	{
		for (int j=1;j<=i;j++) {
			trans[i][j]=((trans[i-1][j]*j)%p+trans[i-1][j-1])%p;
		}
	}
}
inline ll S(ll g,ll k)
{
	return trans[g][k];
}
int main()
{
	freopen("haoi2020_problem.in","r",stdin);
	freopen("haoi2020_problem.out","w",stdout);
	scanf("%lld%lld%lld%lld",&n,&x,&p,&m);
	for(R ll i=0;i<=m;i++)
	{
		scanf("%lld",&a[i]);
	}
	init(p);
	g_h_y=(a[0]*qpow((x+1)%p,n,p))%p;
	for(R ll i=1;i<=m;i++)
	{
		ll tot=(qpow(x%p,i,p)*qpow((x+1)%p,n-i,p)%p)%p;
		ll val=0;
		for(R ll j=0;j<=i-1;j++)
		{
			tot=(tot*(n-j))%p;
		}
		for(R ll j=i;j<=m;j++)
		{
			val=(val+(S(j,i)*a[j])%p)%p;
		}
		g_h_y=(g_h_y+(val*tot)%p)%p;
	}
	printf("%lld\n",g_h_y);
	return 0;
}