【题解|Jzzhu and Sequences(规律，矩阵)】题意:Fi=F(i-1)+F(i+1),现给出F1和F2，问Fn
第一个做法：找规律，列举发现F是循环的，每次循环的长度为6，所以只需要求出前六个就可以得到答案。
#include
#include
#include
#includeusing namespace std;
typedef long long ll;
const int N = 2e5 + 10;
int arr[N];
const ll mod = 1e9 + 7;
ll fac[7];
int main() {
int n;
cin >> fac[1] >> fac[2] >> n;
fac[1] = (fac[1] + mod) % mod;
fac[2] = (fac[2] + mod) % mod;
for (int i = 3;
i <= 6;
i++) {
fac[i] = (fac[i - 1] - fac[i - 2] + mod) % mod;
}
int top = (n % 6 == 0) ? 6 : n % 6;
cout << fac[top] << endl;
} 第二种做法：这种方法就是傻乎乎的去求Fn了，将原式移项得到F(i+1)=Fi+F(i-1),我们用矩阵快速幂求，我们有这样一个关系式：
文章图片
所以要求Fn，我们需要求出前一个矩阵rax的n-2次方，然后再相乘就可ok了，虽然人懒，做其他的事又不想做，又回来写了一下消磨时间
#include
#include
#include
#includeusing namespace std;
typedef long long ll;
const int N = 2e5 + 10;
int arr[N];
const ll mod = 1e9 + 7;
struct matrix {
ll rix[5][5];
}ans,test;
ll quick_pow(ll a,ll b) {
ll ans = 1;
a %= mod;
while (b) {
if (b & 1) ans = (ans + a) % mod;
a = (a + a) % mod;
b >>= 1;
}
return ans;
}matrix mul(int n,matrix rix1,matrix rix2) {
matrix temp;
memset(temp.rix, 0, sizeof(temp.rix));
for (int i = 1;
i <= n;
i++) {
for (int j = 1;
j <= n;
j++) {
for (int k = 1;
k <= n;
k++) {
temp.rix[i][j] = (temp.rix[i][j] + rix1.rix[i][k] * rix2.rix[k][j])%mod;
}
}
}
return temp;
}void quick_rix(int n,int k) {
memset(ans.rix, 0, sizeof(ans.rix));
for (int i = 1;
i <= n;
i++) ans.rix[i][i] = 1;
while (k) {
if (k & 1) ans = mul(n,ans,test);
test = mul(n, test, test);
k >>= 1;
}
//return ans;
}int main() {
ios::sync_with_stdio(false);
matrix rax;
int n;
memset(rax.rix, 0, sizeof(rax.rix));
cin >> rax.rix[2][1] >> rax.rix[1][1];
memset(test.rix, 0, sizeof(test.rix));
test.rix[1][1] = test.rix[2][1] = 1;
test.rix[1][2] = -1;
cin >> n;
if (n == 1) {
cout << (rax.rix[2][1]+mod)%mod< 推荐阅读
- C++|C++浇水装置问题
- 题解|【HNOI2017】大佬-dalao
- 2019 GDUT Rating Contest #II 这是群题解，七篇！！！
- # 2019 GDUT Rating Contest #I H. Mixing Milk
- # 2019 GDUT Rating Contest #I A. The Bucket List
- # 2019 GDUT Rating Contest #I G. Back and Forth
- 2019 GDUT Winter Personal Training Contest III (Div. 2) A题 QAQ 题解
- 2019 GDUT Winter Personal Training Contest I (Div. 2) A. Protect Sheep
- 矩阵快速幂-CodeForces 450B Jzzhu and Sequences
- 题解|题解 | K-ary Heap-2019牛客暑期多校训练营第六场F题