自动搬运

查看原文

来自洛谷，原作者为

	SDqwq 少年何妨梦摘星，敢挽桑弓射玉衡。

搬运于2025-08-24 21:28:09，当前版本为作者最后更新于2021-03-16 23:33:45，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

P1707 刷题比赛

更坏的阅读体验

前置芝士：矩阵

$\texttt{Description}$

给定 $3$ 个序列 $a,b,c$：

$$a_1=b_1=c_1=1$$ $$a_2=b_2=c_2=3$$

计算方式：

$$a_{k+2}=pa_{k+1}+qa_k+b_{k+1}+c_{k+1}+rk^2+tk+1$$ $$b_{k+2}=ub_{k+1}+vb_k+a_{k+1}+c_{k+1}+w^k$$ $$c_{k+2}=xc_{k+1}+yc_k+a_{k+1}+b_{k+1}+z^k+k+2$$

其中 $p,q,r,t,u,v,w,x,y,z$ 都为给定常数。

求 $a_n,b_n,c_n$，答案对 $m$ 取模。

---

数据范围：

$4\le n\le10^{16}$

$2\le m\le10^{16}$

$1\le p,q,r,t,u,v,w,x,y,z\le100$

$\texttt{Solution}$

因为暴力人人都会，所以直接上正解。

每次转移的项数都很少，而 $n$ 很大，所以自然而然地想到了矩阵加速。

不难想到 $1\times11$ 的状态矩阵初始应该长这样子：

$$\begin{bmatrix} a_{k+1}&b_{k+1}&c_{k+1}&a_k&b_k&c_k&k^2&k&1&w^k&z^k \end{bmatrix} $$

于是 $11\times11$ 的转移矩阵随便画一下就出来了：

$$\begin{bmatrix} p&1&1&1&0&0&0&0&0&0&0\\ 1&u&1&0&1&0&0&0&0&0&0\\ 1&1&x&0&0&1&0&0&0&0&0\\ q&0&0&0&0&0&0&0&0&0&0\\ 0&v&0&0&0&0&0&0&0&0&0\\ 0&0&y&0&0&0&0&0&0&0&0\\ r&0&0&0&0&0&1&0&0&0&0\\ t&0&1&0&0&0&2&1&0&0&0\\ 1&0&2&0&0&0&1&1&1&0&0\\ 0&1&0&0&0&0&0&0&0&w&0\\ 0&0&1&0&0&0&0&0&0&0&z \end{bmatrix} $$

接下来矩阵快速幂即可。

---

注意因为模数太大，所以要用龟速乘。

---

时间复杂度：$\mathcal{O}(\log n\log m)$，有个 $11^3$ 的 常数。

$\texttt{Code}$

#include <cstdio>
#include <iostream>
#include <cstring>

using namespace std;

typedef long long ll;

ll m, p, q, r, t, u, v, w, x, y, z;

struct Matrix {
	int n, m;
	ll a[15][15];
	
	inline Matrix () {
		memset(a, 0, sizeof(a));
	}
} base, ans;

inline ll quickMul (ll a, ll b) {
	ll res = 0;
	a %= m;
	b %= m;
	while (b) {
		if (b & 1)
			res = (res + a) % m;
		b >>= 1;
		a = (a + a) % m;
	}
	return res;
}

inline Matrix operator * (Matrix a, Matrix b) {
	Matrix res;
	res.n = a.n;
	res.m = b.m;
	for (int i = 1; i <= a.n; i++)
		for (int j = 1; j <= b.m; j++)
			for (int k = 1; k <= a.m; k++)
				res.a[i][j] = (res.a[i][j] + quickMul(a.a[i][k], b.a[k][j])) % m;
	return res;
}

inline Matrix quickPow (Matrix a, ll k) {
	Matrix res;
	res.n = res.m = a.n;
	for (int i = 1; i <= a.n; i++)
		res.a[i][i] = 1;
	while (k) {
		if (k & 1)
			res = res * a;
		k >>= 1;
		a = a * a;
	}
	return res;
}

inline void init_base () {
	base.n = base.m = 11;
	base.a[1][2] = base.a[1][3] = base.a[1][4] = base.a[2][1] = base.a[2][3] = base.a[2][5] = base.a[3][1] = base.a[3][2] = base.a[3][6] = base.a[7][7] = base.a[8][3] = base.a[8][8] = base.a[9][1] = base.a[9][7] = base.a[9][8] = base.a[9][9] = base.a[10][2] = base.a[11][3] = 1;
	base.a[8][7] = base.a[9][3] = 2;
	base.a[1][1] = p;
	base.a[2][2] = u;
	base.a[3][3] = x;
	base.a[4][1] = q;
	base.a[5][2] = v;
	base.a[6][3] = y;
	base.a[7][1] = r;
	base.a[8][1] = t;
	base.a[10][10] = w;
	base.a[11][11] = z;
}

inline void init_ans () {
	ans.n = 1;
	ans.m = 11;
	ans.a[1][1] = ans.a[1][2] = ans.a[1][3] = 3;
	ans.a[1][4] = ans.a[1][5] = ans.a[1][6] = ans.a[1][7] = ans.a[1][8] = ans.a[1][9] = 1;
	ans.a[1][10] = w;
	ans.a[1][11] = z;
}

int main () {
	ll n;
	scanf("%lld %lld %lld %lld %lld %lld %lld %lld %lld %lld %lld %lld", &n, &m, &p, &q, &r, &t, &u, &v, &w, &x, &y, &z);
	if (n < 2) {
		puts("nodgd 1");
		puts("Ciocio 1");
		puts("Nicole 1");
		return 0;
	}
	init_base();
	init_ans();
	ans = ans * quickPow(base, n - 2);
	printf("nodgd %lld\nCiocio %lld\nNicole %lld", ans.a[1][1], ans.a[1][2], ans.a[1][3]);
	return 0;
}