Luogu P5136 sequence 题解报告

发表于 更新于 分类于

Luogu P5136 sequence 题解。

题目描述

试求出：

⌈(1+52)n⌉ mod 998244353\left \lceil \left ( \frac{1+\sqrt{5}}{2} \right )^{n} \right \rceil \bmod 998244353

多测

题解报告

有一道本题的进阶版：洛谷 P3263 有意义的字符串。

看楼下大佬们都是找规律推递推式，我来一个略有不同的解法（不一样的递推式，主体都为矩乘）。

先不考虑向上取整和取模运算。首先需要将根号去掉，否则会有小数。

可以想到在原式后加上一个 (1−52)n\left ( \frac{1-\sqrt{5}}{2} \right )^{n}，使式子变为：

$ \left ( \frac{1+\sqrt{5}}{2} \right )^{n} + \left ( \frac{1-\sqrt{5}}{2} \right )^{n} $

此时便可以将根号消掉。（注意最后需要减去一个 (1−52)n\left ( \frac{1-\sqrt{5}}{2} \right )^{n}）

我们设 x=(1+52)x= \left ( \frac{1+\sqrt{5}}{2} \right )，y=(1−52)y=\left ( \frac{1-\sqrt{5}}{2} \right )。

再设 f_n=xn+ynf\_{n}=x^{n}+y^{n}。

稍微考虑一下便可得到：

xn+yn=(x+y)(xn−1+yn−1)−xy×(xn−2+yn−2)x^{n}+y^{n}=\left ( x+y \right ) \left ( x^{n-1}+y^{n-1} \right ) -xy \times \left ( x^{n-2}+y^{n-2} \right )

$f_{n}=\left ( x+y \right )f_{n-1}-xy \times f_{n-2} $

这个就是我们的递推式啦。

其中有些东西可以直接算出来：x+y=1x+y=1，xy=−1xy=-1，f_0=1f\_{0}=1，f_1=2f\_{1}=2，f_2=3f\_{2}=3。

于是乎我们的矩阵就很容易地得出来了：

需要由 [f_n−1f_n−2]\begin{bmatrix} f\_{n-1} &f\_{n-2}\end{bmatrix} 推得 [f_nf_n−1]\begin{bmatrix} f\_{n} &f\_{n-1}\end{bmatrix}。

转移矩阵如下：

[11 10]\begin{bmatrix} 1 &1 \\\ 1 &0\end{bmatrix}

最后再来看看减去的那个式子对最终答案的影响：

注意最后需要减去一个 (1−52)n\left ( \frac{1-\sqrt{5}}{2} \right )^{n}

注意到 (1−52)\left ( \frac{1-\sqrt{5}}{2} \right ) 是一个在 (−1,0]\left ( -1,0 \right ] 上的负小数。

当 nn 为偶数时，−(1−52)-\left ( \frac{1-\sqrt{5}}{2} \right ) 为负，由于是向上取整，所以此时该式对答案没有影响。

当 nn 为奇数时，−(1−52)-\left ( \frac{1-\sqrt{5}}{2} \right ) 为正，因为向上取整，最终答案需要加一。

综上，该式对答案有影响，当且仅当 nn 为奇数。

最后到了大家最爱的代码时光。

嗲吗

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#define int long long
const int MOD = 998244353;
struct mat 
{
	int a[2][2];
	mat() { memset(a, 0, sizeof a); }
	mat operator *(const mat &b)const 
	{
		mat op;
		for (int i = 0; i < 2; i++)
			for (int k = 0; k < 2; k++)
				for (int j = 0; j < 2; j++)
					op.a[i][j] = (op.a[i][j] + a[i][k] * b.a[k][j]) % MOD;
		return op;
	}
} ans, I;
void init() 
{
	I.a[0][0] = I.a[0][1] = I.a[1][0] = 1;
	I.a[1][1] = 0;
	ans.a[0][0] = 3, ans.a[0][1] = 1;
	ans.a[1][0] = ans.a[1][1] = 0;
}
signed main() 
{
	int T = read();
	while (T--) 
	{
		n = read();
		init();
		if (n == 0) 
		{
			printf("1\n");
			continue;
		}else if (n == 1) 
		{
			printf("2\n");
			continue;
		}
		int ff = 0;
		if (n % 2 == 1)ff++;
		n -= 2;
		while (n) 
		{
			if (n & 1)ans = ans * I;
			I = I * I;
			n >>= 1;
		}
		ans.a[0][0] += ff;
		printf("%lld \n", ans.a[0][0]);
	}
	return 0;
}

有错误请 D 我。