Mathematics (fast power)

One 、 Fast power

By fast exponentiation , We calculated a^8 when , No more a*a*a*a*a*a*a*a, It is a*a,a^2*a^2,a^4*a^4, So we ask a^b It will be O(log b) Complexity

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;
}

Two 、 Matrix fast power

Use fast power , You can find a matrix （ Matrix ） Of n The next power

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 Matrix cumulative power , When an odd number is encountered, multiply it to res On 
		multi(a, a);			//a=a*a
		m >>= 1;
	}
	// The final answer is 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';
	}
}

Structure version , Overloaded multiplication operator

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';
	}
}

application ： When we need to find a recurrence of the first n term （ for example ） when , You can use matrix multiplication , By exponentiating the matrix, we get the n term