TopCoder SRM 766 : Div1 Easy Div2 Hard HockeyPlayoff

参加してたらMedium早解きでレート50位上がりそうだったのでもったいない…。
https://community.topcoder.com/stat?c=problem_statement&pm=15701

問題

AB２チームでホッケーのゲームを行い、シーズンの勝者を決める。
その際、2試合ごとにAとBのホームで交互に試合を行い、それぞれの勝率が与えられる。
また、直前で片方のチームがW連勝していた場合、5*Wパーセント勝率が上がる。

先にN回ゲームで勝ったチームがシーズンの勝者となる。
Aチームがシーズンの勝者となる確率を求めよ。

解法

以下の状態を考える。
f(a,b,w) := Aチームがa回、Bチームがb回勝利し、直前にどちらかのチームが連勝した回数をwとする(負の場合Bチームが連勝したとみなす)場合に、最終的にAチームがシーズンの勝者となる確率。
a,b,wから次のゲームでAチームが勝つ確率がわかるので、両チームが勝つケースの重みづけ平均を取ればよい。
連勝数は20以上考える必要が無いので、wは-20～20までだけ考えればよい。

ll dp[601][601][50];
ll mo=1000000007;
ll r100;

ll modpow(ll a, ll n = mo-2) {
	ll r=1;a%=mo;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

class HockeyPlayoff {
	public:
	int AW,BW,W;
	ll hoge(int A,int B,int T) {
		if(A==W||T==20) return 1;
		if(B==W||T==-20) return 0;
		if(dp[A][B][T+25]>=0) return dp[A][B][T+25];
		
		int awin;
		if((A+B)%4<2) awin=AW;
		else awin=100-BW;
		awin=min(100,max(0,awin+T*5));
		
		ll ret=0;
		dp[A][B][T+25]=0;
		if(awin) ret+=awin*hoge(A+1,B,min(20,max(0,T)+1));
		if(awin<100) ret+=(100-awin)*hoge(A,B+1,max(-20,min(0,T)-1));
		ret=ret%mo*r100%mo;
		
		return dp[A][B][T+25]=ret;
	}
	
	int winProbability(int winsNeeded, int AwinHome, int BwinHome) {
		AW=AwinHome;
		BW=BwinHome;
		W=winsNeeded;
		MINUS(dp);
		r100=modpow(100);
		
		ll ret=hoge(0,0,0);
		int i;
		FOR(i,2*W-1) ret=ret*100%mo;
		return ret;
		
	}
}

まとめ

最初なんかTLEすると思ったら、100の逆数を毎回計算してるのがまずかった。