牛客挑战赛65 - C 233的数列

原题链接：https://ac.nowcoder.com/acm/contest/48458/C

题意：给你三个序列，他们之间满足一些递推式，求这三个序列前n项，每项的乘积之和

做法：可以发现 $A_n\ast b_n\ast C_{n}A\_n*b\_n*C\_n$ 可以拆成9项由 $A_{n-1},B_{n-1},C_{n-1}A\_\{n-1\},\; B\_\{n-1\},\; C\_\{n-1\}$ 组成的式子，我们定义答案 $D_n={\sum }_{i=1}^{n-1}{A}_n\ast b_n\ast C_{n}D\_n=\backslash sum\_\{i=1\}^\; \{n-1\}A\_n*b\_n*C\_n$，接下来我们考虑将 $D_{n}D\_n$ 和 $A_n\ast b_n\ast C_{n}A\_n*b\_n*C\_n$ 以及上述的9项放入矩阵并构建每一项的递推关系，可以得到递推矩阵，然后就可以开始愉快的矩阵快速幂了

#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
const int MAXN = 11;
ll mod;
struct matrix
{
	ll a[MAXN][MAXN];
	void init(ll in[MAXN][MAXN])
	{
		for (int i = 0; i < MAXN; i++)
			for (int j = 0; j < MAXN; j++)
				a[i][j] = in[i][j];
	}
	void zero()
	{
		for (int i = 0; i < MAXN; i++)
			for (int j = 0; j < MAXN; j++)
				a[i][j] = 0;
	}
	void one()
	{
		for (int i = 0; i < MAXN; i++)
			for (int j = 0; j < MAXN; j++)
				a[i][j] = (i == j ? 1 : 0);
	}
	matrix operator * (const matrix o)
	{
		matrix ans;
		ans.zero();
		for (int i = 0; i < MAXN; i++)
			for (int j = 0; j < MAXN; j++)
				for (int k = 0; k < MAXN; k++)
					ans.a[i][j] = (ans.a[i][j] + this->a[i][k] * o.a[k][j]) % mod;
		return ans;
	}
};
matrix power(matrix a, ll b)
{
	matrix ans;
	ans.one();
	while (b)
	{
		if (b & 1)
			ans = ans * a;
		a = a * a;
		b >>= 1;
	}
	return ans;
}
int main()
{
	ll n, A, B, C, a, b, c, d, e, f;
	sc("%lld%lld%lld%lld%lld%lld%lld%lld%lld%lld%lld", &n, &A, &B, &C, &a, &b, &c, &d, &e, &f, &mod);
	A %= mod;
	B %= mod;
	C %= mod;
	ll pre[MAXN][MAXN] = {
		{0,A * A * A,B * B * B,C * C * C,A * A * B,A * A * C,B * B * C,A * B * B,A * C * C,B * C * C,A * B * C}
	};
	ll mid[MAXN][MAXN] = {
		{1,0,0,0,0,0,0,0,0,0,0},
		{0,a * a * a,c * c * c,e * e * e,a * a * c,a * a * e,c * c * e,a * c * c,a * e * e,c * e * e,a * c * e},
		{0,b * b * b,0,f * f * f,0,b * b * f,0,0,b * f * f,0,0},
		{0,0,d * d * d,0,0,0,0,0,0,0,0},
		{0,3 * a * a * b,0,3 * e * e * f,2 * a * b * c,2 * a * e * b + a * a * f,c * c * f,b * c * c,2 * e * a * f + e * e * b,2 * e * c * f,a * c * f + b * c * e},
		{0,0,3 * c * c * d,0,a * a * d,0,2 * e * c * d,2 * a * c * d,0,e * e * d,a * d * e},
		{0,0,0,0,b * b * d,0,0,0,0,d * f * f,b * d * f},
		{0,3 * a * b * b,0,3 * e * f * f,b * b * c,e * b * b + 2 * a * b * f,0,0,a * f * f + 2 * e * b * f,c * f * f,b * c * f},
		{0,0,3 * c * d * d,0,0,0,e * d * d,a * d * d,0,0,0},
		{0,0,0,0,0,0,d * d * f,b*d*d,0,0,0},
		{1,0,0,0,2 * a * b * d,0,2 * c * d * f,2 * b * c * d,0,2 * e * d * f,a * d * f + b * d * e},
	};
	matrix one;
	one.init(pre);
	matrix qq;
	qq.init(mid);
	one = one * power(qq, n);
	pr("%lld\n", one.a[0][0]);
	//pr("\n");
	//vector<ll>va = { A }, vb = { B }, vc = { C };
	//ll sum = A * B * C;
	//for (int i = 0; i < n - 1; i++)
	//{
	//	va.push_back((a * va[i] + b * vb[i]) % mod);
	//	vb.push_back((c * va[i] + d * vc[i]) % mod);
	//	vc.push_back((e * va[i] + f * vb[i]) % mod);
	//	sum = (sum + va[i + 1] * vb[i + 1] * vc[i + 1]) % mod;
	//}
	//cout << sum;
}
/*
3 3 2 3 3 2 3 3 2 3 23
*/