记录编号	612729	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[统一省选 2020]组合数问题	最终得分	100
用户昵称	对立猫猫对立	是否通过	通过
代码语言	C++	运行时间	0.347 s
提交时间	2026-02-25 20:36:24	内存使用	3.28 MiB

#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int n, x, P, m, f[N], g[N], a[N];
int fastpow(int x, int y)
{
	int ans = 1;
	for (; y; y >>= 1, x = 1ll * x * x % P)
		if (y & 1) ans = 1ll * ans * x % P;
	return ans;
}
int main()
{
	cin >> n >> x >> P >> m;
	for (int i = 0; i <= m; i++) cin >> a[i];
	f[0] = fastpow(x + 1, n - m);
	for (int i = m - 1; ~i; i--)
	{
		g[0] = 1ll * f[0] * (x + 1) % P;
		for (int j = 1; j <= m - i; j++)
			g[j] = 1ll * (g[j - 1] - f[j - 1] + P) % P * (n - i) % P;
		for (int j = 0; j <= m - i; j++) f[j] = g[j];
	}
	int ans = 0;
	for (int i = 0; i <= m; i++) ans = (ans + 1ll * f[i] * a[i]) % P;
	cout << ans << endl;
	return 0;
}