@OceanEye7年前
04/8
18:42
伤心事.裸题居然还交了6次才A。
感觉如果不压行的话我的代码应该还是很容易懂的吧……
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
#include #include #include #include using namespace std; long long square[4][4],fib[4]; long long n; void pow() { int i,j,k; long long a[4][4]; for(i=1;i<=2;i++) for(j=1;j<=2;j++) { a[i][j]=square[i][j]; square[i][j]=0; } // memset(square,0,sizeof(square)); for(i=1;i<=2;i++) for(j=1;j<=2;j++) for(k=1;k<=2;k++) square[i][j] += a[i][k]*a[k][j]; for(i=1;i<=2;i++) for(j=1;j<=2;j++){ square[i][j]%=10; if (square[i][j]<0) square[i][j]+=10; } } void solve(long long x) { while(x>0) { if(x&1) { long long aa[4]; aa[1] = fib[1];aa[2] = fib[2]; fib[1] = aa[1]*square[1][1] + aa[2]*square[2][1]; fib[1]%=10; if (fib[1]<0) fib[1]+=10; fib[2] = aa[1]*square[1][2] + aa[2]*square[2][2]; fib[2]%=10; if (fib[2]<0) fib[2]+=10; } pow(); x>>=1; } } int main() { scanf("%lld",&n); fib[1]=1; fib[2]=1; square[1][1] = 0; square[1][2] = 1; square[2][1] = 1; square[2][2] = 1; solve(n); printf("%lld\n",fib[1]); return 0; } |