September Cook-Off 2012 PTOSS : Pizza Tossing

問題概要

長さN,M(<10^6)のビット列S,Tが与えられる。Sの部分文字列としてTが出てくるまでランダムにSの末尾に0or1を付け加える。付け加えられる個数の期待値をmodで求める問題。答は整数になることを示せる。

解法

末尾がn文字一致している状態から必要な個数の期待値をE[n]とする。failure linkを用いて連立一次方程式を立式できる。このとき、各iについてE[i]=P[i]+Q[i]*E[0]とおくことによってE[N]=P[N]+Q[N]*E[0]までDPで計算できる。あとはE[N]=0を解いてE[0]を出せば各iについてE[i]を求めることができる。

acceptされたコード

const int MAX_L = int(1e6);

char buf[MAX_L/5 + 1], S[MAX_L + 1], T[MAX_L + 1];
int Slen, Tlen;
int fail[MAX_L], towards[MAX_L];
int64 cons[MAX_L + 1], coef[MAX_L + 1];

int64 inv(int64 x) {
	return calcPow(x, MOD - 2);
}

void buildFailureLink(){
	int j = fail[0] = -1;
	for (int i = 1; i <= Slen; i++) {
		while( j >= 0 && S[j] != S[i-1]){
			j = fail[j];
		}
		fail[i] = ++j;
	}
}

int KMP_search(){
	int i, j;
	for(i=0, j=0; i<Tlen; i++){
		while(j >= 0 && T[i] != S[j]){
			j = fail[j];
		}
		if( ++j == Slen ){
			return Slen;
			j = fail[j];
		}
	}

	return j;
}

inline int decode(char ch) {
	if (islower(ch)) {
		return ch - 'a' + 0;
	}
	else {
		return ch - 'A' + 26;
	}
}

inline void init() {
	scanf("%d %s", &Slen, buf);
	for (int i = 0, p = 0; buf[i]; ++i) {
		const int a = decode(buf[i]);
		for (int j = 5 - 1 ; j >= 0; --j) {
			S[p++] = char('0' + ((a>>j)&1));
		}
	}
	S[Slen] = '\0';
	scanf("%d %s", &Tlen, buf);
	for (int i = 0, p = 0; buf[i]; ++i) {
		const int a = decode(buf[i]);
		for (int j = 5 - 1 ; j >= 0; --j) {
			T[p++] = char('0' + ((a>>j)&1));
		}
	}
	T[Tlen] = '\0';
}

int solve() {
	buildFailureLink();
	const int k = KMP_search();
	if (k == Slen) {
		return 0;
	}
	fail[0] = 0;
	coef[0] = 1;
	cons[0] = 0;
	towards[0] = 0;

	for (int i = 0; i < Slen; ++i) {
		if (i > 0) {
			char nxt = S[i];
			towards[i] = (nxt != S[fail[i]] ? fail[i] + 1: towards[fail[i]]);
		}
		coef[i+1] = (2 * coef[i] - coef[towards[i]] + MOD) % MOD;
		cons[i+1] = (2 * cons[i] - cons[towards[i]] - 2 + 2*MOD) % MOD;
	}

	int64 e0 = inv(coef[Slen]) * (MOD - cons[Slen]) % MOD;
	return (cons[k] + coef[k] * e0) % MOD;
}