Mushroom Gnomes

题面

很久以前，在蘑菇森林的灌木丛中生活着蘑菇地精。它们以神奇的蘑菇而在邻居中闻名。它们的神奇特性使得它们每分钟可以在相邻的两个蘑菇之间长出另一个蘑菇，而该蘑菇的重量等于两个相邻蘑菇的重量之和。

蘑菇地精喜欢一切都井井有条的，这就是为什么它们总是按照重量递增的顺序将蘑菇种成一行。

地精们种下蘑菇后就去吃饭了。 $x$ 分钟后，他们返回，发现新的蘑菇长大了，因此打破了递增的顺序。

地精们按照正确的顺序重新种植了所有蘑菇，也就是说，他们按照重量递增的顺序重新对蘑菇进行了排序。然后又去吃饭了（地精们是食量很大的）。 再过 $y$ 分钟，蘑菇总重量对 $p$ 取模的值是多少？

题解

有意思的题。

一次的和为 $s_i=3s_{i-1}-a_1-a_n$ ，两次矩阵快速幂。对于第二次矩阵快速幂，它的两端：最小为 $a_1$ ，最大值由斐波那契数列，手玩发现是 $f_{i-1}a_{n-1}+f_{i}a_n$ 。

代码

const int N = 1e6 + 5, M = 5;

inline ll Read() {
	ll x = 0, f = 1;
	char c = getchar();
	while (c != '-' && (c < '0' || c > '9')) c = getchar();
	if (c == '-') f = -f, c = getchar();
	while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
	return x * f;
}

namespace Main {
	int n;
	ll x, y, mod, sum;
	ll a[N];

	struct Matrix {
		int n, m;
		ll mat[M][M];
		void zero() { for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) mat[i][j] = 0; }
		ll* operator [] (int x) { return mat[x]; }
		void output () { for (int i = 1; i <= n; i++, putchar(10)) for (int j = 1; j <= m; j++) printf("%lld ", mat[i][j]);}
	} init, trans, fib;

	Matrix operator *(Matrix a, Matrix b) {
		Matrix c;
		c.n = a.n, c.m = b.m;
        memset (c.mat, 0, sizeof c.mat);
		for (int i = 1; i <= c.n; i++) {
			for (int j = 1; j <= c.m; j++) {
				for (int k = 1; k <= c.n; k++) 
					(c.mat[i][j] += a.mat[i][k] * b.mat[k][j] % mod) %= mod;
			}
		}
		return c;
	}
	Matrix qpow (Matrix a, ll b) {
		Matrix ans; ans.n = ans.m = a.n;
        memset (ans.mat, 0, sizeof ans.mat);
		for (int i = 1; i <= ans.n; i++) ans[i][i] = 1ll;
		for (; b; b >>= 1, a = a * a) 
			if (b & 1) ans = ans * a;
		return ans;
	}

	int main () {
		n = Read(), x = Read(), y = Read(), mod = Read();
		for (int i = 1; i <= n; i++) (sum += (a[i] = Read())) %= mod;
		fib.n = fib.m = trans.n = trans.m = init.n = 2, init.m = 1;
		trans[1][1] = 3, trans[1][2] = -1, trans[2][1] = 0, trans[2][2] = 1;
		init[1][1] = sum, init[2][1] = (a[1] + a[n]) % mod;
		fib[1][1] = fib[1][2] = fib[2][1] = 1;
		fib = qpow(fib, x);
		Matrix step = qpow(trans, x);
//		cerr << step[1][1] << ' ' << step[1][2] << endl;
		init = step * init;
		(init[2][1] = a[1] + (fib[1][1] * a[n] % mod + fib[2][1] * a[n - 1] % mod) % mod) %= mod;
		step = qpow(trans, y);
		init = step * init;
		for (; init[1][1] < 0; init[1][1] += mod);
		printf ("%lld\n", init[1][1]);
		return 0;
	}
}

int main () {
//	freopen(".in", "r", stdin);
//	freopen(".out", "w", stdout);
	Main::main();
	return 0;
}