#include<bits/stdc++.h>
using namespace std;

int main(){
	int a[1000005],i,n,m,num;
	cin>>n;
	a[1] = 1;a[2] = 2;a[3] = 5;
	for(i = 4;i<=n;i++){
		a[i]+=((a[i-1]*2)%10000)+((a[i-3])%10000);
		a[i]%=10000;
	}
	cout<<a[n]<<endl;
	system ("pause");
}

完全式求助！

顺便问一句关于状态转移方程其原理到底是什么啊aaaa