yukicoder No.533 Mysterious Stairs

問題はこちら
No.533 Mysterious Stairs - yukicoder

初期値にちょっと気をつける必要があるがDPやるだけ。
dp[昇った段数合計][直前に段数]=場合の数

dp[1000010][4];n;
mod=1000000007;
main(){
	dp[1][1]=1;
	dp[2][2]=1;
	dp[3][1]=dp[3][2]=dp[3][3]=1;
	scanf("%d",&n);
	for(int i=4;i<=n;i++){
		dp[i][1]=(dp[i-1][2]+dp[i-1][3])%mod;
		dp[i][2]=(dp[i-2][1]+dp[i-2][3])%mod;
		dp[i][3]=(dp[i-3][1]+dp[i-3][2])%mod;
	}
	printf("%d",(dp[n][1]+dp[n][2]+dp[n][3])%mod);
}

実際には3段前までの情報があればいいので、直前の9状態から次の3状態を生成するDP。
ということは何かいい感じの漸化式ができるのでは……と思いながらOEISを見たらビンゴ
A155822 - OEIS
次の2つの漸化式が書いてあった

引き算が入っているとmodをとる時にこまるのと、単純に式が短い方が嬉しいので後者を採用した
代入が多いのでmain再帰で書いたけど、初期値を与えるもっと簡単な方法はないのだろうか……

n;M=1e9+7;main(a,b,c,d,e,f){~scanf("%d",&n)?main(1,1,3,3,4,8):--n?main(b,c,d,e,f,(0L+d+c+b+a+a)%M):printf("%d",a);}

115B

2017/07/29追記
自明な2B

n;M=1e9+7;main(a,b,c,d,e,f){~scanf("%d",&n)?main(1,1,3,3,4,8):--n?main(b,c,d,e,f,(2L*a+b+c+d)%M):printf("%d",a);}

113B