AcWing 1304. 佳佳的斐波那契
题意
佳佳对数学,尤其对数列十分感兴趣。
在研究完 $Fibonacci$ 数列后,他创造出许多稀奇古怪的数列。
例如用 $S(n)$ 表示 $Fibonacci$ 前 $n$ 项和 $mod \ m$ 的值,即 $S(n)=(F1+F2+…+Fn)mod \ m$ ,其中 $ F1=F2=1,Fi=Fi−1+Fi−2F1=F2=1,Fi=Fi−1+Fi−2$。
可这对佳佳来说还是小菜一碟。
终于,她找到了一个自己解决不了的问题。
用 $T(n)=(F1+2F2+3F3+…+nFn)mod \ m$ 表示 $Fibonacci$ 数列前 $n$ 项变形后的和 $mod \ m$ 的值。
现在佳佳告诉你了一个 $n$ 和 $m$,请求出 $T(n)$ 的值。
输入格式
共一行,包含两个整数 $n$ 和 $m$。
输出格式
共一行,输出 $T(n)$ 的值。
数据范围
$1≤n,m≤2^{31}−1$
输入样例:
5 5
输出样例:
1
样例解释
$T(5)=(1+2×1+3×2+4×3+5×5)mod \ 5=1$
题解
$$ T(n) = (F_1+2F_2+3F_3+…+nF_n)mod \ m \\ T(n) = ((n-(n-1))F_1+(n-(n-2))F_2+(n-(n-3))F_3+…+(n-(n-n)F_n)mod \ m \\ T(n) = n(F_1+F_2+…+F_n) - ((n-1)F_1 + (n-2)F_2 + (n-3)F_3 + … + (n-n)F_n) \\ T(n) = nS_n -(S_{n-1} + S_{n-2} + … + S_2 + S_1) \\ T(n) = nS_n -U_{n-1} \\ $$
$$ S_n = S_{n-1} + F_n \\ F_{n+1} = F_n + F_{n-1} \\ F_{n} = F_{n} \\ \\ \\ $$
所以矩阵为
$$
1 \ 1 \ 0 \\
0 \ 1 \ 1 \\
0 \ 1 \ 0 \\
$$
假设 $U_n = S_1 + S_2 + … + S_n$
$$
U_n = U_{n-1} + S_{n-1} + F_{n}\\
S_{n} = S_{n-1} + F_{n} \\
F_{n+1} = F_{n} + F_{n-1} \\
F_{n} = F_{n} \\
$$
所以矩阵为
$$
1 \ 1 \ 1 \ 0 \\
0 \ 1 \ 1 \ 0 \\
0 \ 0 \ 1 \ 1 \\
0 \ 0 \ 1 \ 0 \\
$$
代码
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
typedef long long ll;
const int mtmaxn = 5;
ll mod;
struct mt {
ll a[mtmaxn][mtmaxn];
int n;
};
mt init(int n) {
mt a;
memset(a.a, 0, sizeof(a.a));
a.n = n;
return a;
}
mt add(mt a, mt b) {
mt c = init(a.n);
for (int i = 0; i < a.n; ++ i) {
for (int j = 0; j < b.n; ++ j) {
c.a[i][j] = (a.a[i][j] + b.a[i][j]) % mod;
}
}
return c;
}
mt mul(mt a, mt b) {
mt c = init(a.n);
for (int i = 0; i < a.n; ++ i) {
for (int j = 0; j < a.n; ++ j) {
for (int k = 0; k < a.n; ++ k) {
c.a[i][j] += (a.a[i][k] * b.a[k][j]) % mod;
c.a[i][j] %= mod;
}
}
}
return c;
}
void Print(mt a) {
for (int i = 0; i < a.n; ++ i) {
for (int j = 0; j < a.n; ++ j) {
cout << a.a[i][j] << " ";
}
cout << endl;
}
cout << endl;
}
mt qpow(mt a, ll b) {
mt c = init(a.n);
for (int i = 0; i < c.n; ++ i) {
c.a[i][i] = 1;
}
while (b) {
if (b & 1) c = mul(c, a);
b /= 2;
a = mul(a, a);
}
return c;
}
int main() {
ll n;
cin >> n >> mod;
mt t;
t.n = 3;
t.a[0][0] = 1, t.a[0][1] = 1, t.a[0][2] = 0;
t.a[1][0] = 0, t.a[1][1] = 1, t.a[1][2] = 1;
t.a[2][0] = 0, t.a[2][1] = 1, t.a[2][2] = 0;
t = qpow(t, n);
ll res = n * t.a[0][1];
res %= mod;
mt s;
s.n = 4;
s.a[0][0] = 1, s.a[0][1] = 1, s.a[0][2] = 1, s.a[0][3] = 0;
s.a[1][0] = 0, s.a[1][1] = 1, s.a[1][2] = 1, s.a[1][3] = 0;
s.a[2][0] = 0, s.a[2][1] = 0, s.a[2][2] = 1, s.a[2][3] = 1;
s.a[3][0] = 0, s.a[3][1] = 0, s.a[3][2] = 1, s.a[3][3] = 0;
s = qpow(s, n-1);
res -= s.a[0][2] % mod;
res = (res % mod + mod) % mod;
cout << res << endl;
return 0;
}