网站seo站长工具,网络平台加盟代理,wordpress调用页面名称,开网店的一年的费用文章目录题目描述题目描述代码题目描述 题目描述
关键在于如何转化为本题的题目。。。 设 y(1-根号5#xff09;/2$$ 再令#xff1a; A(n)xn yn 通过尝试可以发现#xff0c;A其实就是一个1,3为前两项的斐波拉契数列 则 xnA(n)-yn A的值可以用矩阵快速幂来求 而y是在(-1,…
文章目录题目描述题目描述代码题目描述 题目描述
关键在于如何转化为本题的题目。。。 设 y(1-根号5/2$$ 再令 A(n)xn yn 通过尝试可以发现A其实就是一个1,3为前两项的斐波拉契数列 则 xnA(n)-yn A的值可以用矩阵快速幂来求 而y是在(-1,0)的区间 所以分一下n的奇偶性就可以求出答案了
代码
#includebits/stdc.h
using namespace std;
#define ll long long
const int mod1e97;
ll a,b,c,k;
ll ans[4][4],res[4][4],trans[4][4];
void mul1(){//res*resmemset(trans,0,sizeof(trans));for(int i1;i2;i){for(int j1;j2;j){for(int p1;p2;p){trans[i][j]res[i][p]*res[p][j];trans[i][j]%mod;}}}for(int i1;i2;i){for(int j1;j2;j){res[i][j]trans[i][j];}}
}
void mul2(){//res*ansmemset(trans,0,sizeof(trans));for(int i1;i2;i){for(int j1;j2;j){for(int p1;p2;p){trans[i][j]ans[i][p]*res[p][j];trans[i][j]%mod;}}}for(int i1;i2;i){for(int j1;j2;j){ans[i][j]trans[i][j];}}
}
void ksm(ll w){while(w){if(w1) mul2();mul1();w1;}return;
}
void print(){for(int i1;i2;i){for(int j1;j2;j){printf(%d ,ans[i][j]);}printf(\n);}
}
int main()
{ans[1][1]ans[2][2]1;res[1][1]res[1][2]res[2][1]1;scanf(%lld,a);if(a2) {printf(1);return 0;}ksm(a-2);
// print();printf(%lld,(ans[1][1]ans[2][1])%mod);return 0;
}
