洛谷P1962

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod = 1000000007;

struct Matrix {
  int a[3][3];

  Matrix() { memset(a, 0, sizeof a); }

  Matrix operator*(const Matrix &b) const {
    Matrix res;
    for (int i = 1; i <= 2; ++i)
      for (int j = 1; j <= 2; ++j)
        for (int k = 1; k <= 2; ++k)
          res.a[i][j] = (res.a[i][j] + a[i][k] * b.a[k][j]) % mod;
    return res;
  }
} ans, base;

void init() {
  base.a[1][1] = base.a[1][2] = base.a[2][1] = 1;
  ans.a[1][1] = ans.a[1][2] = 1;
}

void qpow(int b) {
  while (b) {
    if (b & 1) ans = ans * base;
    base = base * base;
    b >>= 1;
  }
}

signed main() {
  int n;
  cin>>n;
  if (n <= 2) return puts("1"), 0;
  init();
  qpow(n - 2);
  cout<<ans.a[1][1] % mod;
  return 0;
}

#include <stdio.h> #include <string.h> long long n,mod=10000; void Matrix1(long long a[2],long long b[2][2]) { long long c[2]={0}; for(int j=0;j<2;j++) { for(int k=0;k<2;k++) { c[j]=(c[j]+a[k]*b[k][j]%mod)%mod; } } memcpy(a,c,sizeof(c)); } void Matrix2(long long b[2][2]) { long long c[2][2]={0}; for(int i=0;i<2;i++) { for(int j=0;j<2;j++) { for(int k=0;k<2;k++) { c[i][j]=(c[i][j]+b[i][k]*b[k][j]%mod)%mod; } } } memcpy(b,c,sizeof(c)); } int main() { while(~scanf("%lld",&n)) {
if(n==-1) break; else {
long long a[2]={0,1}; long long b[2][2]={0,1,1,1}; while(n) { if(n&1) Matrix1(a,b); Matrix2(b); n>>=1; } printf("%lld\n",a[0]); } } return 0; }

#include <stdio.h>
#include <string.h>
long long n,mod=10000;
void Matrix1(long long a[2],long long b[2][2])
{
	long long c[2]={0};
	for(int j=0;j<2;j++)
		{
			for(int k=0;k<2;k++)
			{
				c[j]=(c[j]+a[k]*b[k][j]%mod)%mod;
			}
		}
		memcpy(a,c,sizeof(c));
}
void Matrix2(long long b[2][2])
{
	long long c[2][2]={0};
	for(int i=0;i<2;i++)
	{
		for(int j=0;j<2;j++)
		{
			for(int k=0;k<2;k++)
			{
				c[i][j]=(c[i][j]+b[i][k]*b[k][j]%mod)%mod;
			}
		 } 
	}
	memcpy(b,c,sizeof(c));
}
int main()
{
	while(~scanf("%lld",&n))
    {   
        if(n==-1) break;
        else
        {  
            long long a[2]={0,1};
            long long b[2][2]={0,1,1,1};
	        while(n)
	        {
		    if(n&1)	Matrix1(a,b);
		    Matrix2(b);
		    n>>=1;
	        }
	    printf("%lld\n",a[0]);
        }
    }
    return 0;
}