BS 6.9

· · 个人记录

这个，是不是要保密啊。那就不放题意了。

考虑一个点第一次被染黑之后就一直有贡献，所以答案只和每个点的染色时间 t_i 有关。
那么直接转成期望，求 E(res) 后乘上 (n - 1)! 就行了。
直接使用 E(x) = \sum_{i = 0} P(x \gt i)，则

E(t_x) = 1 + \sum_{i = 1}^{n - 1 - siz_x} \dfrac{(n - 1 - siz_x)^{\underline{i}}}{(n - 1)^{\underline{i}}}

同时有 E(res) = \sum_{x} n - E(t_x)。
为了方便，不妨把这里的 n 换成 n - 1，然后 E(t_x) 中加的那个 1 就去掉了。

设 siz'_x = n - 1 - siz_x，则有

E(t_x) = \sum_{i = 1}^{siz'_x} \dfrac{siz'_x! (n - 1 - i)!}{(siz'_x - i)!(n - 1)!} \\ = \dfrac{siz'_x !}{(n - 1)!} \sum_{i = 1}^{siz'_x} (n - 1 - i)^{\underline{siz_x}} \\ = \dfrac{siz'_x !}{(n - 1)!} \sum_{i = siz_x}^{n - 2} i^{\underline{siz_x}}

有个小丑考场上直接把下降幂转成斯特林数然后匹都没推出来，写了个记忆化 O(n^2) 喜提 51 pts。

事实上这玩意就是 nt 东西，你把下降幂换成组合数乘阶乘就有

\sum_{i = x}^{n - 2} i^{\underline{x}} = x! \sum_{i = 0}^{n - 2} \dbinom{i}{x}

这是典中典上指标求和，但是这个小丑他还是不会。所以我们来推一下式子帮帮他罢。

g(n, x) = \sum_{i = 0}^{n} \dbinom{i}{x} \\ = \sum_{i = 0}^{n} (\dbinom{i - 1}{x} + \dbinom{i - 1}{x - 1}) \\ = \sum_{i = 0}^{n - 1} \dbinom{i}{x} + \sum_{i = 0}^{n - 1} \dbinom{i}{x - 1} \\

小丑说这啥也看不出来啊。
你直接把 RHS 的第一项移项：

\dbinom{n}{x} = g(n - 1, x - 1)

没了。这就是通项。

欲赢丁真，鉴定为 _____。

最后换个根就做完了。复杂度 O(n)。

核心代码： 

inline void GetFunction() {
    for(ui i = 1; i <= n - 2; ++i)
        f[i] = 1ull * C(n - 1, i + 1) * fac[i] % p * fac[n - 1 - i] % p;
}

期望的线性性（没人规定一场只能考一次这个东西）：

E(x \mid C) = \sum_{i = 1}^{n} P(a_i = 1 \mid C)

其中 C 是给出的限制。
其实如果不去管它给的那些公式，按照正常的思路去想，应该是只考虑左边对它的限制，也就是直接写成 DDP。
状态很好设，就是 f_{i, 0 / 1} 表示 i 是 0 / 1 的期望为 1 的个数。
注意，如果你写成了 (f_{i, 0 / 1} + 1) \times P(a_{i + 1} = 1 \mid a_{i} = 0 / 1) \to f_{i + 1, 1}，是有问题的。由于这里只考虑了左边的限制，所以直接算条件概率是少考虑了一部分贡献的，不妨先算 \sum P(a_i = 1 \land C)，最后再变回条件概率。所以转移是

(f_{i, 0 / 1} + g_{i, 0 / 1}) \times P(a_{i + 1} = 1 \mid a_{i} = 0 / 1) \to f_{i + 1, 1}

其中 g 为，考虑了之前的特殊限制的情况下，i 为 0 / 1 的概率。
那么需要维护的就是一个 \left[ \begin{array}{c} g_{i, 0} & g_{i, 1} & f_{i, 0} & f_{i, 1} \end{array} \right] 的向量，对于没有限制的 i，从 i - 1 到 i 的转移矩阵是好求的：

\left[ \begin{array}{c} p_{i, 0, 0} & p_{i, 1, 0} & 0 & p_{i, 1, 0} \\ p_{i, 0, 1} & p_{i, 1, 1} & 0 & p_{i, 1, 1} \\ 0 & 0 & p_{i, 0, 0} & p_{i, 1, 0} \\ 0 & 0 & p_{i, 0, 1} & p_{i, 1, 1} \end{array} \right]

对于有限制的部分，考虑让不合法的转移系数为 0，那么直接把非法转移的部分设为 0，其它部分不变，最后答案是 \dfrac{f_0 + f_1}{g_0 + g_1}（这里 dp 出来的是 \sum P(a_i = 1 \land C)，需要求的是 \sum P(a_i = 1 \mid C)，需要除掉一个 P(C) 变成条件概率）

然后就可以做了。直接放到线段树上维护，复杂度 O(n k^3 \log n)，这里 k = 4。应该需要手动循环展开一下之类的。

可以这么写，有一种一种的美。 

struct M {
    db a[4][4]; M() { memset(a, 0, sizeof(a)); }
    inline M operator * (const M &b) const { M t;
    #define U0(i, j, k) t.a[i][j] += a[i][k] * b.a[k][j]
    #define U1(i, j) U0(i, j, 0), U0(i, j, 1), U0(i, j, 2), U0(i, j, 3)
    #define U2(i) U1(i, 0), U1(i, 1), U1(i, 2), U1(i, 3)
        return U2(0), U2(1), U2(2), U2(3), t;
    }
};