TopCoder SRM 762 : Div1 Medium StrawberryHard Div2 Hard Strawberry

うーん。
https://community.topcoder.com/stat?c=problem_statement&pm=15599&rd=17608

問題

２人で以下のゲームを行う。
両者交代で自分のターンを迎える。
自分のターンでは、0～(2K)のいずれかの得点を得られる。
その際の確率は事前に与えられる。

各ターン後、点差がKを超えるならゲームは終了する。
Nターン終えてもゲームが終了しない確率を求めよ。

解法

毎ターン後、点差が-K～Kとなる確率をDPで求めていけばよい。
これでO(NK^2)で解け、Div2 Hardはこれで十分である。
Div1 Mediumは一見TLが厳しいが、128bit型整数を使い除算を避けると4.6sぐらいで通る。
想定解はKaratsuba法らしいし、任意modのNTTでも解けるようだ。

以下は横着O(NK^2)解。

ll mo=1000000007;
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;
}

ll from[14001];
__int128 to[14001];

class StrawberryHard {
	public:
	int competitive(int n, int k, int Arange, int Brange, int seed) {
		vector<ll> A,B;
		ll AS=0,BS=0;
		ll state=seed;
		int i,j,x;
		FOR(i,2*k+1) {
			state = (1103515245 * state + 12345);
			state %= 1LL<<31;
			A.push_back(state%Arange);
			AS+=A.back();
			state = (1103515245 * state + 12345);
			state %= 1LL<<31;
			B.push_back(state%Brange);
			BS+=B.back();
		}
		AS=modpow(AS%mo);
		BS=modpow(BS%mo);
		FORR(a,A) a=a*AS%mo;
		FORR(b,B) b=b*BS%mo;
		
		ZERO(from);
		from[7000]=1;
		FOR(x,n) {
			ZERO(to);
			if(x%2==0) {
				for(i=-k;i<=k;i++) {
					for(j=0;j<=2*k;j++) if(i+j<=k) (to[(i+j)+7000]+=from[i+7000]*A[j]);
				}
			}
			else {
				for(i=-k;i<=k;i++) {
					for(j=0;j<=2*k;j++) if(i-j>=-k) (to[(i-j)+7000]+=from[i+7000]*B[j]);
				}
			}
			for(i=-k;i<=k;i++) from[i+7000]=to[i+7000]%mo;
		}
		ll ret=0;
		for(i=-k;i<=k;i++) ret+=from[i+7000];
		return ret%mo;
		
	}
}

まとめ

さすがにCodeforcesのコメント見ても評判良くないなぁ…。