C - Wall
套路题。。一眼看去以为是组合数学乱搞题。。然后思路想错了。。MDZZ。。。
最后还是用DP搞的。本以为可以一维，不过发现还是要2维，然而某大神看了数列的4个数字就猜出了规律！（好劲啊！！下一代YJQ的节奏！！不管了，先膜一发再说！）
所以。。其实是套路对吧？果然我还是见识的套路少了。。
#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
inline void read(int& x)
{
char c=getchar();bool flag=0;x=0;
while(c<'0'||c>'9'){if(c=='-')flag=true;c=getchar();}
while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
flag?x=-x:1;
}
#define mod 10000
#define maxn 1000010
int n;
long long ans ,dp[maxn][5];
int main(void)
{
#define ACK
#ifdef ACK
freopen("wall.in","r",stdin);
freopen("wall.out","w",stdout);
#endif
read(n);
dp[1][0]=1;
dp[2][1]=1;
dp[2][2]=1;
dp[2][0]=2;
for(int i=3;i<=n;i++)
{
dp[i][0]+=dp[i-1][0]+dp[i-1][1]+dp[i-1][2];
if(i>1)dp[i][0]+=dp[i-2][0];
if(i>1)dp[i][1]+=dp[i-1][2]+dp[i-2][0];
if(i>1)dp[i][2]+=dp[i-1][1]+dp[i-2][0];
dp[i][0]%=mod;
dp[i][1]%=mod;
dp[i][2]%=mod;
}
// for(int i=1;i<=5;i++)cout<<i<<"->"<<dp[i][0]<<endl;
cout<<dp[n][0]%mod;
return 0;
}正解DP，可以用滚动数组优化。难得优化了，反正又不会MLE