C++14(g++5.4) 解法, 执行用时: 4ms, 内存消耗: 364K, 提交时间: 2020-06-02 10:33:09

#include<bits/stdc++.h>
using namespace std;
const int p=10000;
int n;
void mul(int f[2],int a[2][2]) {
	int c[2]= {};
//	memset(c,0,sizeof(c));
	for(int i=0; i<2; i++)
		for(int j=0; j<2; j++) {
			c[i]=(c[i]+(long long)f[j]*a[j][i])%p;
		}
	memcpy(f,c,sizeof(c));
}
void mulself(int a[2][2]) {
	int c[2][2]= {};
//	memset(c,0,sizeof(c));
	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]+(long long)a[i][k]*a[k][j])%p;
	memcpy(a,c,sizeof(c));
}
int main() {
	while(cin>>n&&n!=-1) {
		int f[2]= {0,1},a[2][2]= {0,1,1,1};
		for(; n; n>>=1) {
			if(n&1)mul(f,a);
			mulself(a);
		}
		cout<<f[0]<<endl;
	}
	return 0;
}

C++ 解法, 执行用时: 38ms, 内存消耗: 792K, 提交时间: 2021-12-31 17:23:36

#include<bits/stdc++.h>
using namespace std;
int a[100001],n;
int pv(int n){
	a[0]=0;
	a[1]=1;
	for(int i=2;i<100001;i++)a[i]=(a[i-1]+a[i-2])%10000;
	return a[n%15000]%10000;
} 
int main(){
	while(cin>>n&&n!=-1)cout<<pv(n)<<"\n";
	return 0;
}