梦熊第二届省选挑战赛 T2 炫酷原神 genshin 唐氏记录

需要复制一段文字，具体来说给定一个字符串 si，然后你有一个剪贴板，初始为空，和一个初始为空的字符串 t，然后对于所有 1 到 n 的 i，小水母会依次进行如下操作：

• "Ctrl + C" 操作，将剪贴板的内容修改为 si。
• "Ctrl + V" 操作，将剪贴板的内容添加到 t 末尾。
  每次 "Ctrl + C" 操作和 "Ctrl + V" 操作都只有一半概率成功。

求最终串 t 的期望权值，其定义为多少个子串只有一种字符。Q 次单点修改 si，你需要输出每次修改后的答案。（n,Q<=2e5）

记得往简单了想。

对于一个字符，最好是求以每个位置结尾，向前最长连续段期望长度。

（强制结尾思想的完全运用。）

枚举这个字符。对于每个位置 i，要求它必须 Ctrl-V，此时剪贴板内字符显然必须为 si，这个概率①容易计算。

//NOI-MRA-3004 zhouziqi
//pw[i]:=2**i
//ipw[i]:=pw[i]**(-1)
void DP(char c, int op) {
    for (int i = 1; i <= n; i ++) {
        sum[i] = sum[i - 1];
        if (s[i] == c) {
            add(sum[i], pw[i - 1]);
        }
    }

    for (int i = 1, s0 = 0, s1 = 0; i <= n; i ++) {
        int f = ((long long){sum[i]} * ipw[i + 1]  //①
              + ((long long){sum[i]} * s0 + s1) % P * ipw[i << 1]) % P;
        if (op > 0) {
            add(ans, f);
        } else {
            add(ans, P - f);
        }

        int mul = (long long){pw[i]} * f % P;
        add(s0, mul);
        add(s1, (long long){pw[i] - sum[i] + P} * mul % P);
    }
}