题意：
就是给出你一个斐波那契数列，让你求第n项，n小于等于10的1e6次方。
题解：
斐波那契数列用矩阵快速幂求就行，这里不能二进制快速幂，需要转换到十进制快速幂，学到了
还有,一定要记得初始化，不然怎么超时的自己都不知道。
代码：
#include <bits/stdc++.h> using namespace std; #define ll long long ll mod; char s[1000010]; struct node{ ll m[2][2]; node(){ memset(m,0,sizeof(m)); } friend node operator *(node a,node b) { node ans; for(int i=0;i<2;i++) { for(int j=0;j<2;j++){ ans.m[i][j] = 0; for(int k=0;k<2;k++){ ans.m[i][j] = (a.m[i][k]*b.m[k][j] + ans.m[i][j])%mod; } } } return ans; } }; node pow(node a,int k) { node ans; ans.m[0][0] = ans.m[1][1] = 1; ans.m[0][1] = ans.m[1][0] = 0; while(k) { if(k&1) ans = ans*a; k >>= 1; a = a*a; } return ans; } node ans,e; int main() { ll a,b,c,d; scanf("%lld%lld%lld%lld",&a,&b,&c,&d); scanf("%s %lld",s,&mod); int len = strlen(s); ans.m[0][0] = ans.m[1][1] = 1; ans.m[1][0] = ans.m[0][1] = 0; e.m[0][0] = c,e.m[0][1] = d,e.m[1][0] = 1; e.m[1][1] = 0; for(int i=len-1;i>=0;i--) { ans = ans * pow(e,s[i] - '0'); e = pow(e,10); } cout<<((b*ans.m[1][0]) + (a*ans.m[1][1]))%mod<<endl; return 0; }
```
京公网安备 11010502036488号