C++ 解法, 执行用时: 6ms, 内存消耗: 304K, 提交时间: 2022-05-29 17:09:09

#include<iostream>
#include<algorithm>
using namespace std;
const int MOD = 10000;
string s;
int main()
{
    while(cin>>s)
    {
        if(s=="-1") break;
       int n;
    int res=0;
    for(int i=0;i<s.size();i++)
    {
        res=(res*10+(s[i]-'0'))%15000;
    }
    if(res==0) n=15000;
    else n=res;
    int b=1;
    //cout<<1<<' '<<1<<' ';
    int cnt=1;
    for(int i=3;i<=n;i++)
    {
        int t=cnt%MOD;
        cnt=(cnt+b)%MOD;
        b=t;
        //cout<<cnt<<' ';
//         if(cnt==1) {
//             cout<<i<<endl;
//             break;
//         }
    }
    cout<<cnt<<endl; 
    }
    
    return 0;
}

C++(g++ 7.5.0) 解法, 执行用时: 2ms, 内存消耗: 188K, 提交时间: 2022-09-10 09:05:29

#include<cstdio>
void mul(int*a,int*b,int*c)
{
	c[0]=(a[0]*b[0]+a[1]*b[2])%10000;
	c[1]=(a[0]*b[1]+a[1]*b[3])%10000;
	c[2]=(a[2]*b[0]+a[3]*b[2])%10000;
	c[3]=(a[2]*b[1]+a[3]*b[3])%10000;
}
int work(int n)
{
	int a[4]={1,0,0,1},b[4]={1,1,1,0},c[4]={};
	while(n)
	{
		if(n&1)mul(a,b,c),__builtin_memcpy(a,c,16);
		mul(b,b,c),__builtin_memcpy(b,c,16);
		n>>=1;
	}
	return a[1];
}
int main()
{
	while(1){int n;scanf("%d",&n);if(!~n)return 0;printf("%d\n",work(n));}
}

C 解法, 执行用时: 8ms, 内存消耗: 364K, 提交时间: 2021-07-19 09:40:26

#include <stdio.h>
#include <stdlib.h>
int main()
{
    int i,yu,a[3];
    long long n,shang;
    while(~scanf("%lld",&n))
    {
     n=n%30000;
     if(n>=0)
     {
      a[0]=0;
      a[1]=1;
      yu=n%3;
      shang=(n+1-(n+1)%3)/3;
    
      for(i=1;i<=shang;i++)
      {
       a[2]=(a[1]+a[0])%10000;
       a[0]=(a[1]+a[2])%10000;
       a[1]=(a[2]+a[0])%10000;
      }
    
      printf("%d\n",a[yu]);
     }
    }
    return 0;
}