贵州遵义企业公司网站建设,seo包年优化,icp许可证个人网站,有没有做奥数题的网站相信我们都做过一个题叫斐波那契数列#xff0c;对于一般的题#xff0c;n的取值范围通常在1000以内#xff0c;但是如果你遇到的是下面这题呢#xff1f;
斐波那契数列 - 洛谷 发现了吗#xff1f;我的n取值范围连long long都会爆出#xff0c;所以下面我们通过矩阵乘法…相信我们都做过一个题叫斐波那契数列对于一般的题n的取值范围通常在1000以内但是如果你遇到的是下面这题呢
斐波那契数列 - 洛谷 发现了吗我的n取值范围连long long都会爆出所以下面我们通过矩阵乘法和快速幂结合来解决该类问题如果你不知道矩阵乘法和快速幂这篇文章可能不适合你
下面我们利用矩阵乘法和快速幂来解决该问题
代码如下
#include bits/stdc.h
using namespace std;
using lllong long;
const ll p1e97;
ll x;
const int N2;
int n2;
ll a[N1][N1],b[N1];void func1()
{ll m[N1];memset(m,0,sizeof(m));for(int i1;in;i){for(int j1;jn;j){m[i]b[j]*a[j][i];m[i]%p;}}memcpy(b,m,sizeof(b));
}
void func2()
{ll w[N1][N1];memset(w,0,sizeof(w));for(int i1;in;i){for(int j1;jn;j){for(int k1;kn;k){w[i][j]a[i][k]*a[k][j];w[i][j]%p;}}}memcpy(a,w,sizeof(a));
}
void quickpow(ll x)
{for(;x;x1){if(x1){func1();}func2();}
}
int main()
{//输入cinx;//快速幂矩阵乘法//初始化a[1][1]0;a[1][2]1;a[2][1]1;a[2][2]1;b[1]0;b[2]1;quickpow(x-1);//输出coutb[2];return 0;
}
可以优化
#include bits/stdc.h
using namespace std;
using lllong long;
const ll p1e97;
ll x;
const int N2;
int n2;
ll a[N1][N1],b[N1];void func1()
{ll m[N1];memset(m,0,sizeof(m));for(int i1;in;i){for(int j1;jn;j){m[i]b[j]*a[j][i];m[i]%p;}}memcpy(b,m,sizeof(b));
}
void func2()
{ll w[N1][N1];memset(w,0,sizeof(w));for(int i1;in;i){for(int k1;kn;k){if(a[i][k]){for(int j1;jn;j){if(a[k][j]){w[i][j]a[i][k]*a[k][j];w[i][j]%p;}}}}}memcpy(a,w,sizeof(a));
}
void quickpow(ll x)
{for(;x;x1){if(x1){func1();}func2();}
}
int main()
{//输入cinx;//快速幂矩阵乘法//初始化a[1][1]0;a[1][2]1;a[2][1]1;a[2][2]1;b[1]0;b[2]1;quickpow(x-1);//输出coutb[2];return 0;
} 下面我们给出矩阵乘法和快速幂结合模版该类问题解题关机是构造矩阵
using ll long long;
const ll N 2;//实际情况修改
int n 2;
ll a[N 1][N 1], b[N 1];
const ll p 1e8 7;//取模的值
void func1()
{ll m[N 1];//清空memset(m, 0, sizeof(m));for (int i 1; i n; i){for (int j 1; j n; j){m[i] a[j][i] * b[j];m[i] % p;}}memcpy(b, m, sizeof(b));
}
void func2()
{ll w[N 1][N 1];memset(w, 0, sizeof(w));/*for (int i 1; i n; i){for (int j 1; j n; j){for (int k 1; k n; k){w[i][j] a[i][k] * a[k][j];w[i][j] % p;}}}*///优化for (int i 1; i n; i){for (int k 1; k n; k){if (a[i][k]){for (int j 1; j n; j){if (a[k][j]){w[i][j] a[i][k] * a[k][j];w[i][j] % p;}}}}}memcpy(a, w, sizeof(a));
}
void quickpow(ll x)
{for (; x; x 1){if (x 1){func1();}func2();}
} 关于这类问题很多网址都有大量题目大家可以自行去学习感谢大家的支持
