問題B：完全立方数を避ける数列選択

数列 $\{a_n\}$ から部分集合を選び、任意の2要素の積が完全立方数とならないようにする。$n\le 10^5$、$1\le a_i\le 10^{10}$。

重要な観察：$10^5$ より大きい素因数を持つ数は常に解答に寄与する。その他の数については、非1の完全立方因子をすべて除去してから処理する。

ll factorizeRandom(ll val) {
    if (val % 2 == 0) return 2;
    ll diff, ptr1, ptr2, param;
    while (true) {
        diff = 1;
        for (int step = 1; step <= 256; step <<= 1) {
            ptr1 = ptr2 = 0;
            param = rng() % (val - 1) + 1;
            for (int iter = 1; iter <= step; iter++) {
                ptr1 = iterate(iterate(ptr1, param, val), param, val);
                ptr2 = iterate(ptr2, param, val);
                diff = multiply(diff, abs(ptr1 - ptr2), val);
            }
            ll g = __gcd(diff, val);
            if (g != 1) return g;
        }
    }
}

Pollard-Rhoアルゴリズムの実装例。ランダムシードの選択が重要で、233では一部のテストケースでTLEを発生させる。

問題C：オンライン文字列照合

文字列 $s$ と複数のクエリ文字列 $t$ が与えられる。各クエリについて、$t$ が $s$ 中に出現する回数を答える。オンラインで処理する必要がある。

$|s|, q, |t|, \sum |t| \le 10^5$、$|\Sigma|=10^6$。

解法戦略：クエリ長で分割し、短いものはKMP、長いものはハッシュを使用する。全体の計算量は $O(n\sqrt{n}\log n)$ に抑えられる。

void buildHash() {
    powBase[0] = 1;
    for (int i = 1; i <= MAXLEN; i++) 
        powBase[i] = powBase[i-1] * HASH_BASE;
    for (int i = 1; i <= ALPHABET_SIZE; i++) 
        charHash[i] = rng();
}

int queryKMP(int qlen, vector<int>& pattern, vector<int>& text) {
    vector<int> combined(qlen + text.size() + 1);
    for (int i = 0; i < qlen; i++) combined[i] = pattern[i];
    combined[qlen] = -1;
    for (int i = 0; i < text.size(); i++) combined[qlen + 1 + i] = text[i];
    
    vector<int> fail(combined.size(), 0);
    for (int i = 1; i < combined.size(); i++) {
        int j = fail[i-1];
        while (j > 0 && combined[i] != combined[j]) j = fail[j-1];
        if (combined[i] == combined[j]) j++;
        fail[i] = j;
    }
    
    int count = 0;
    for (int i = qlen + 1; i < combined.size(); i++) {
        if (fail[i] == qlen) count++;
    }
    return count;
}

問題D：最適化部分列問題

2つの排列 $S$ と $G$（長さ $n$）と整数 $k$ が与えられる。$i \in [n-k+1, n]$ に対して、$G[i:n]$ をランダムに並び替えられる。この操作で、ある部分列 $S[x:y]$ を並び替えたものが $G[l:r]$ と一致するような区間 $[l,r]$ の数を最大化する。

$k \le n \le 2\times10^5$。

この問題では、排列の局所的な再配置がグローバルなパターンマッチングにどう影響するかを分析する必要がある。