SRM475 Div1Medium

解法：シミュレーションするだけ。modまわりが面倒。
一年の流れの順番が難しくて遷移も考えづらいし、MOD計算もややこしい。と思ったら逆元かけるだけだった。mod 1000000009で2の逆元とか自明だった…

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
typedef unsigned long long wolf;
class RabbitIncreasing{
	public:
	wolf y[3];
	int ans[3];
	int getNumber(vector<int>a,int b){
		if(a[0]==1)return 0;
		int MOD=1000000009;
		y[0]=1;
		y[1]=0;
		ans[0]=1;ans[1]=0;
		int index=0;
		for(int i=1;i<=b;i++){

			if(a[index]==i){
				index++;
				if((y[1]+y[0])&1){
					y[1]-=(y[1]+y[0]+1)/2;
					ans[1]=((long long)ans[1]-(long long)(ans[0]+ans[1]+1)*500000005)%MOD;
					if(ans[1]<0)ans[1]+=MOD;
				}else{
					y[1]-=(y[0]+y[1])/2;
					ans[1]=(long long)((long long)ans[1]-(long long)(ans[0]+ans[1])*500000005)%MOD;
					if(ans[1]<0)ans[1]+=MOD;
				}
			}
			if(i==b)break;
		//	printf("%d %d\n",ans[0],ans[1]);
			wolf c=y[1];
			y[1]+=y[0];
			y[0]=c;
			int d=ans[1];
			ans[1]=(ans[1]+ans[0])%MOD;
			ans[0]=d;			

		}return (ans[0]+ans[1])%MOD;
	}
};