矩阵快速幂

const int mod = 1e9 + 7;
struct mat
{
	ll m[3][3];
	mat()
	{
		for (int i = 0; i < 3; i++)
			for (int j = 0; j < 3; j++)
				m[i][j] = 0;
	}
};

mat mul(mat a, mat b)
{
	mat temp;
	for (int i = 0; i < 3; i++)
		for (int j = 0; j < 3; j++)
			for (int k = 0; k < 3; k++)
				temp.m[i][j] = (temp.m[i][j] + a.m[i][k] * b.m[k][j]) % mod;
	return temp;
}

mat qp(mat a, ll b)
{
	mat ans;
	for (int i = 0; i < 3; i++)
		ans.m[i][i] = 1;
	while (b)
	{
		if (b & 1)
			ans = mul(ans, a);
		a = mul(a, a);
		b >>= 1;
	}
	return ans;
}

留下评论