AT_abc200_f 题解

Melo.VVちゃん · 2026-05-12 17:01:34 · 题解

感觉糖糖的。

考虑一个确定的串的答案是极长 0 段和 1 段数量的较小者，进一步发现如果一个串的开头字符是 1，那么答案一定等于极长 0 段的数量，反之亦然。

于是直接钦定开头字符，然后在每个极长段的开头计算贡献，以计算极长 0 段数量为例，对于一个位置 i，他可以作为极长段开头的充要条件是 i 位置的字符不是 1，且 i-1 位置不是 0，枚举所有这样的位置，他对答案的贡献显然是 2^{tot-a-b}，其中 tot 表示 ? 总数，a,b 为一表示 i,i-1 是 ?，否则为 0。

然后发现对于在模 |S| 意义下相等的位的答案必然一样，那么起码可以做到 O(|S|\log K|S|)。

当第一个字符是 ? 需要两种情况都算一遍，所以第一个出现的 T 比较特殊，单独拎出来处理即可。

需要特判 |S|=1 的 corner。

    f (i ,1 ,n ,1) pre[i] = pre[i - 1] + (ch[i] == '?') ;
    int tot = pre[n] ;

    auto Qpow = [] (int p ,int bs = 2) -> int {
        if (p < 0) return 0 ;
        p %= mod - 1 ;
        int res = 1 ;
        for (; p ; p >>= 1 ,bs = 1ll * bs * bs % mod)
            (p & 1) && (res = 1ll * res * bs % mod) ; 
        return res ;
    } ;

    if (n == 1) {
        if (ch[1] != '?') return std :: cout << "0\n" ,0 ;
        else std :: cout << 2ll * ((1ll * (k - 2) * Qpow (k - 3) % mod + Qpow (k - 2)) % mod) % mod << '\n' ;
        return 0 ;
    }

    if (ch[1] == '0') {
        int ans = 0 ;
        f (i ,2 ,n ,1) if (ch[i] != '0' && ch[i - 1] != '1')
            (ans += Qpow (pre[i - 2] + tot * (k - 1) + pre[n] - pre[i]) % mod) %= mod ;
        if (k > 1) f (i ,1 ,n ,1) if (ch[i] != '0' && ch[i == 1 ? n : i - 1] != '1') {
            int coef = i == 1 ? pre[n - 1] : tot + pre[i - 2] ;
            (ans += 1ll * (k - 1) * Qpow (coef + tot * (k - 2) + pre[n] - pre[i]) % mod) %= mod ;
        } std :: cout << ans << '\n' ;
    } else if (ch[1] == '1') {
        int ans = 0 ;
        f (i ,2 ,n ,1) if (ch[i] != '1' && ch[i - 1] != '0')
            (ans += Qpow (pre[i - 2] + tot * (k - 1) + pre[n] - pre[i]) % mod) %= mod ;
        if (k > 1) f (i ,1 ,n ,1) if (ch[i] != '1' && ch[i == 1 ? n : i - 1] != '0') {
            int coef = i == 1 ? pre[n - 1] : tot + pre[i - 2] ;
            (ans += 1ll * (k - 1) * Qpow (coef + tot * (k - 2) + pre[n] - pre[i]) % mod) %= mod ;
        } std :: cout << ans << '\n' ;
    } else {
        std :: for_each (pre + 1 ,pre + n + 1 ,[] (int &i) -> void { i-- ;}) ;

        int ans = 0 ;
        ch[1] = '0' ; f (i ,2 ,n ,1) if (ch[i] != '0' && ch[i - 1] != '1')
            (ans += Qpow (pre[i - 2] + tot * (k - 1) + pre[n] - pre[i]) % mod) %= mod ;
        if (k > 1) f (i ,1 ,n ,1) if (ch[i] != '0' && ch[i == 1 ? n : i - 1] != '1') {
            int coef = i == 1 ? pre[n - 1] : tot + pre[i - 2] ;
            (ans += 1ll * (k - 1) * Qpow (coef + tot * (k - 2) + pre[n] - pre[i]) % mod) %= mod ;
        }

        ch[1] = '1' ; f (i ,2 ,n ,1) if (ch[i] != '1' && ch[i - 1] != '0') 
            (ans += Qpow (pre[i - 2] + tot * (k - 1) + pre[n] - pre[i]) % mod) %= mod ;
        if (k > 1) f (i ,1 ,n ,1) if (ch[i] != '1' && ch[i == 1 ? n : i - 1] != '0') {
            int coef = i == 1 ? pre[n - 1] : tot + pre[i - 2] ;
            (ans += 1ll * (k - 1) * Qpow (coef + tot * (k - 2) + pre[n] - pre[i]) % mod) %= mod ;
        } std :: cout << ans << '\n' ;
    }