f(x+1)=f(x)+f(x?1)+sin(πx2)。
正常fibonacci就是
1 1 1 0
然后旋轉矩陣： 0 1 0 0 0 0 1 0 0 0 0 1 1 0 0 0
最后： [ 1 1 1 0 0 0 ] , [ 1 0 0 0 0 0 ] , [ 0 0 0 1 0 0 ] , [ 0 0 0 0 1 0 ] , [ 0 0 0 0 0 1 ] , [ 0 0 1 0 0 0 ] 他得n-2乘上[f2,f1,0,-1,0,1]T 因為sin是循環的~就好了
#include <cstdio>#include <iostream>#include <cstring>using namespace std;const long long MOD = 1000000007;struct Matrix{ long long m[6][6];};long long aa,bb,nn;Matrix Mul(Matrix a ,Matrix b){ Matrix tmp; memset(tmp.m,0,sizeof(tmp.m)); for(int i = 0 ; i < 6 ; i++) for(int j = 0 ; j < 6 ;j++) for(int k = 0 ; k < 6; k++) tmp.m[i][j] = (tmp.m[i][j]+a.m[i][k]*b.m[k][j])%MOD ; return tmp;}Matrix qpow(Matrix a,long long n){ Matrix tmp; memset(tmp.m,0,sizeof(tmp.m)); for(long long i = 0 ; i < 6 ;i++) tmp.m[i][i] = 1; while(n){ if(n & 1) tmp = Mul(tmp,a); n>>=1; a = Mul(a,a); } return tmp;}void sov(){ Matrix tmp; memset(tmp.m,0,sizeof(tmp.m)); tmp.m[0][0] = tmp.m[0][1] = tmp.m[0][2] = tmp.m[1][0] = tmp.m[2][3] = tmp.m[3][4] = tmp.m[4][5] = tmp.m[5][2] = 1; tmp = qpow(tmp,nn-2); long long ans = ((bb*tmp.m[0][0]+aa*tmp.m[0][1]-tmp.m[0][3]+tmp.m[0][5])%MOD+MOD)%MOD; cout<<ans<<"/n";}int main(){ while(cin>>aa>>bb>>nn){ if(nn == 1) cout<<aa<<"/n"; else if(nn == 2) cout<<bb<<"/n"; else sov(); }}新聞熱點
疑難解答
