C++ 解法, 执行用时: 312ms, 内存消耗: 2728K, 提交时间: 2022-05-06 21:32:14

#include <bits/stdc++.h>

#define N 1000010
#define lint long long
#define For(i, j) for(int i=0;i<3;++i)for(int j=0;j<3;++j)

using namespace std;

inline int read() {
	int x; char c;
	while (!isdigit(c = getchar())); x = c ^ 48;
	while (isdigit(c = getchar())) x = x * 10 + (c ^ 48);
	return x;
}

int f0, f1, mod, n;
inline void madd(int &a, int b) { a += b; if (a >= mod) a-= mod; }

struct Matrix {
	int a[3][3];
	inline Matrix operator * (const Matrix& o) const {
		Matrix r;
		For(i, j) r.a[i][j] = 0;
		for (int k = 0; k < 3; ++k)
			For(i, j) madd(r.a[i][j], 1ll * a[i][k] * o.a[k][j] % mod);
		return r;
	}
} xx[40000], yy[40000];

const Matrix tra = {
	0, 1, 0,
	1, 1, 1,
	0, 2, 1
};

int main() {
	f0 = read(), f1 = read(), mod = read(), n = read();
	
	For(i, j) xx[0].a[i][j] = yy[0].a[i][j] = i == j;
	int t = sqrt(1e9) + 1;
	cerr << t;
	for (int i = 1; i <= t; ++i) xx[i] = xx[i - 1] * tra;
	for (int i = 1; i <= t; ++i) yy[i] = yy[i - 1] * xx[t];
	
	int ans = 1;
	for (int i = 1; i <= n; ++i) {
		int x = read() - 1;
		Matrix a = xx[x % t] * yy[x / t];
		int res = 0;
		madd(res, 1ll * f0 * a.a[0][1] % mod);
		madd(res, 1ll * f1 * a.a[1][1] % mod);
		madd(res, (lint)sqrt(3 + 1ll * f0 * f1) * a.a[2][1] % mod);
		ans = 1ll * ans * res % mod;
	}
	
	cout << ans;
	
	return 0;
}