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; }