SRM 541 div1 med: AkariDaisukiDiv1

問題

TopCoder Statistics - Problem Statement

string X に対して, f(X) = W+X+A+X+D と定義する(+ は文字列をつなぎ合わせることを表すオペレータ)。
また, f^k(X) = f(f^(k-1)(X)) と定義する。

f^k(S) の中に, 文字列 F が何回現れるかを数えよ。

解法

「X に F が cnt 回現れているときに, f(X) には F が何回現れるか」という問題を考えます。f(X) には X が 2 回出てくるので, 少なくとも 2*cnt 回は出現します。また,

• (W の後半) + (X の前半)
• (X の後半) + (A) + (X の前半)
• (X の後半) + (D の前半)

という文字列のつなぎあわせでも F が出てくる可能性があります(これで出てくる F の個数を x とする)。これらは, F の文字数を M として, X の最初の M 文字と X の後ろの M 文字を覚えておけば対応できます。

これで k が小さい時はクリアです。k がそこそこ大きい場合は, これでは計算量が O(M^2*k) かかる(工夫して O(MK) にしても定数倍重い)ので死にます。
ですが, f^k(X) で得られる文字列は, 前半が W を k 個並べた形に, 後半が D を k 個並べた形になることに注目すると, k が十分大きい場合には X の前半と後半は変化しないことがわかります。よって, k が十分大きい場合は, x は変化しなくなるので, cnt = (2*cnt+x) を k 回繰り返すだけになります。これは O(k) または O(log k) で計算できるので間に合います。

const ll MOD = 1e9+7;

// s の中に t がどれだけあるか
ll calc(const string s, const string& t, int start) {
    int n = s.size(), m = t.size();
    ll ret = 0;
    for (int i = start; i < n; i++) {
        if (s.substr(i, m) == t) ret++;
    }
    return ret;
}

class AkariDaisukiDiv1 {
public:
    int countF(string W, string A, string D, string S, string F, int k) {
        while (S.size() < F.size() && k > 0) {
            k--;
            S = W+S+A+S+D;
        }
        int N = S.size(), M = F.size();
        ll cnt = 0;
        for (int i = 0; i < N; i++) {
            if (S.substr(i, M) == F) cnt++;
        }
        if (!k) return cnt;
        string f = S.substr(0, M), b = S.substr(N-M);
        int t = 100;
        ll x = 0;
        while (t>0 && k>0) {
            t--; k--;
            x = 0;
            x += calc(W+f, F, 0);
            x += calc(b+A+f, F, 1);
            x -= 2*calc(f, F, 0);
            x += calc(b+D, F, 1);
            cnt = (2*cnt+x)%MOD;
            f = W+f;
            f = f.substr(0, M);
            b = b+D;
            b = b.substr(b.size()-M);
        }
        while (k > 0) {
            k--;
            cnt = (2*cnt+x)%MOD;
        }
        return cnt;
    }
};