题解：P14860 [ICPC 2021 Yokohama R] Cancer DNA

lyht · 2026-01-19 15:28:59 · 题解

题目传送门

省流：这个 5\% 也太大了！

Solution

直接容斥可以 \mathcal{O}(2^n\operatorname{poly}(nm))。

这个在 n 比较大的时候就炸了，思来想去，你会发现并没有什么很对的做法，然后看到这个 5\%，也是把「乱搞」写你脸上了。

考虑将 n 个 DNA 一个一个加进来，加进来一个 T 会使答案增加 P，P 为随机一个 S 使得 S 不与之前已加的 DNA 匹配但与 T 匹配的概率。

这个东西随机 S（随法就是将 T 中的 ? 换成随机的）就行了。

Code

代码里的 C 自己取。

signed main() {
    // freopen("", "r", stdin);
    // freopen("", "w", stdout);
    read(m, n);
    for (int i = 1; i <= n; ++i) {
        read(s[i]); int c = 0;
        for (int _ = C; _--; ) {
            string t = s[i];
            for (char &c : t) if (c == '?') c = "ACGT"[rnd() % 4];
            for (int j = 1, k; j < i; ++j) {
                for (k = 0; k < m; ++k) if (s[j][k] ^ '?' && s[j][k] ^ t[k]) break;
                if (k == m) goto brek;
            } ++c;
            brek: ;
        }
        ans += pow(0.25, m - count(s[i].begin(), s[i].end(), '?')) / C * c;
    }
    cout << ans;
    return 0;
}