TopCoder SRM 475 Div 1 Medium RabbitIncreasing

こういう問題すらすら解けるようになりたいorz
デバッグ力もないし、とりわけ方針があやふやだからバグが何処にあるのかわからずはまって疑心暗鬼になり時間だけを浪費する。

問題概要

ある国の、1年目の7/1に一組のウサギのつがいがいる。
毎年3/1に満一歳以上のつがいはオスとメスの子供を生む。
毎年4/1にオスとメスのウサギはつがいになる
leavingで与えられた年の11/1には、つがいの半分（切り上げ）は国の外へ出る。
国へ出るつがいは年齢が高いほうから順に選ばれる。
k年目の12/1に国内にいるウサギの数をmod1,000,000,009で求めよ。

leavingの要素は50個以下、kは10000000以下である。

解法

11月の時点での今年誕生したウサギをY0[i],昨年誕生したウサギをY1[i],一昨年以前に誕生したウサギをY2[i]とすると、leavingの年の12月には歳をとってるほうから半分いなくなるので、Y2[i]=0, Y1[i]/=2になる。

翌年はウサギが歳をとって、子を産むので
Y2[i]=Y2[i-1]+Y1[i-1], Y1[i]=Y0[i-1], Y0[i]=Y2[i]

modでの割り算は逆元をかければいい。
ウサギが偶数か奇数か判定するのは、最初mod2でウサギの数を別にもって置けばいいのかな？と思ったのだが、一度割った後はmod2では偶数か奇数かもうわからなくなる。
mod 2^（たくさん）で持っておけばよい。

unsigned long longを使うと自動でmod 2^64されるのでmodする手間が省ける。(とLayCurseさんがブログで言ってた。なるほど。）

1年目にウサギがいなくなる場合はコーナーケースなので別途処理。

ソースコード

typedef unsigned long long ll;
const int mod=1000000009,inv_2=500000005;

ll Y2[2],Y1[2],Y0[2],X2[2],X1[2],X0[2];
bool lv[10000001];

class RabbitIncreasing {
	public:
	int getNumber(vector <int> leaving, int k) 
	{
		
		int n=leaving.size();
		rep(i,2)Y2[i]=Y1[i]=Y0[i]=X2[i]=X1[i]=X0[i]=0;
		rep(i,k+1)lv[i]=0;
		rep(i,n)lv[leaving[i]]=1;
		
		if(leaving[0]==1)return 0;
		
		int cur=0,prev=1;
		
		X0[cur]=Y0[cur]=1;
		X1[cur]=X2[cur]=0;
		for(int i=2;i<=k;i++)
		{
			swap(cur,prev);
			Y0[cur]=(Y2[prev]+Y1[prev])%mod; Y1[cur]=Y0[prev]; Y2[cur]=Y0[cur];
			X0[cur]=X2[prev]+X1[prev]; X1[cur]=X0[prev]; X2[cur]=X0[cur];
			
			if(!lv[i])continue;
			
			Y2[cur]=X2[cur]=0; Y1[cur]-=X1[cur]%2;
			Y1[cur]=Y1[cur]*inv_2%mod;
			X1[cur]/=2;
		}
		return (Y0[cur]+Y1[cur]+Y2[cur])%mod;
	}
};