3.16
#include<iostream> #include<cstring> #include<cstdio> using namespace std; int a[2][2],b[2][2],n; void mul(int a[2][2],int b[2][2],int ans[2][2]){ int t[2][2]; memset(t,0,sizeof(t)); for(int i=0;i<=1;i++) for(int j=0;j<=1;j++) for(int k=0;k<=1;k++) t[i][j]=(t[i][j]+a[i][k]*b[k][j])%10000; for(int i=0;i<=1;i++) for(int j=0;j<=1;j++) ans[i][j]=t[i][j]; } int main(){ while(scanf("%d",&n)!=EOF){ a[0][0]=a[0][1]=a[1][0]=b[0][0]=b[1][1]=1; b[1][0]=b[0][1]=a[1][1]=0; if(n==-1)return 0; while(n){ if(n&1)mul(a,b,b);//b=a*b; n>>=1;//n/=2; mul(a,a,a);//a*=a; } printf("%d\n",b[1][0]); } }
8.12
#include<iostream> #include<cstdio> using namespace std; inline int read() { int x = 0, f = 1; char ch = getchar(); while (ch < '0' || ch > '9') { if (ch == '-')f = -1; ch = getchar(); } while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); } return x*f; } struct M { int a[2][2]; } a; inline M operator *(const M &a, const M &b) { M res; for (int i = 0; i < 2; ++i) for (int j = 0; j < 2; ++j) { res.a[i][j] = 0; for (int k = 0; k < 2; ++k) res.a[i][j] = (res.a[i][j] + a.a[i][k] * b.a[k][j]) % 10000; } return res; } inline M operator ^ (M a, int n) { M res = a; for (--n; n; n >>= 1, a = a * a) if (n & 1)res = res * a; return res; } int n; int main() { while (~scanf("%d", &n)) { if (n == -1)return 0; if (n == 0) { printf("0\n"); continue; } a.a[0][0] = a.a[0][1] = a.a[1][0] = 1; a.a[1][1] = 0; a = a^n; printf("%d\n", a.a[1][0]); } }