数学（快速幂）

一、快速幂

通过快速幂，我们计算a^8时，不再是a*a*a*a*a*a*a*a，而是a*a，a^2*a^2，a^4*a^4，这样我们求a^b将是O(log b)的复杂度

ll quick_pow(ll a, ll b)
{
	ll ans = 1;
	while (b)
	{
		if (b & 1)
			ans = (ans * a) % mod;
		b >>= 1;
		a = (a * a) % mod;
	}
	return ans;
}

二、矩阵快速幂

利用快速幂，可以求一个矩阵（方阵）的n次幂

ll temp[maxn][maxn];
ll res[maxn][maxn];
ll a[maxn][maxn];
ll n, m;
void multi(ll a[][maxn], ll b[][maxn])
{
	memset(temp, 0, sizeof temp);
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			for (int k = 0; k < n; k++)
				temp[i][j] = (temp[i][j] + a[i][k] * b[k][j]) % mod;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			a[i][j] = temp[i][j];
}
void qpow(ll a[][maxn], ll m)
{
	memset(res, 0, sizeof(res));
	for (int i = 0; i < n; i++)
		res[i][i] = 1;
	while (m)
	{
		if (m & 1)
			multi(res, a);		//res=res*a， a矩阵累积次方，当遇到奇数时乘到res上
		multi(a, a);			//a=a*a
		m >>= 1;
	}
	//最后答案是res
}
void solve()
{
	cin >> n >> m;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			cin >> a[i][j];
		}
	}
	qpow(a, m);
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			cout << res[i][j] << ' ';
		}
		cout << '\n';
	}
}

结构体版本，重载乘法运算符

struct mat
{
	int a[maxn][maxn];
	int* operator [] (int i)
	{
		return a[i];
	}
	mat() { memset(a, 0, sizeof a); }
	mat operator * (mat b)
	{
		mat res;
		for (int i = 0; i < maxn; i++)
			for (int j = 0; j < maxn; j++)
				for (int k = 0; k < maxn; k++)
					(res[i][j] += 1LL * a[i][k] * b[k][j] % mod) %= mod;
		return res;
	}
};
mat qpow(mat a, ll n)
{
	mat res;
	for (int i = 0; i < maxn; i++)
	{
		res.a[i][i] = 1;
	}
	while (n)
	{
		if (n & 1)
			res = res * a;
		a = a * a, n >>= 1;
	}
	return res;
}
void solve()
{
	mat a;
	ll n, m;
	cin >> n >> m;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			cin >> a[i][j];
		}
	}
	a = qpow(a, m);
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			cout << a[i][j] << ' ';
		}
		cout << '\n';
	}
}

应用：当我们需要求一个递推式的第n项（例如）时，可以利用矩阵乘法，通过对矩阵求幂得到第n项