A
什么时候改一下不用脑子的毛病。
音符的判定分相互独立且容易计算。
考虑如何计算连击分。
直接把 \(\texttt{Perfect}\) 和 \(\texttt{Good}\) 的概率求和记为 \(a\)，不连击记为 \(c\)。
枚举最长连击长度 \(len\)，记 \(f_{i, j, 0/1}\) 表示前 \(i\) 个音符，当前连击 \(j\) 次，是否达成要求。
那么
不难发现这个只有和到新的 \(0\) 的转移以及全局乘并把数组最后一项丢掉。
可以维护全局和以及全局乘的值就可以优化到 \(O(n)\)。
B
不会 FWT
位矩阵
记 \(\text{FWT}\) 的贡献系数为 \(c(i, j)\)，即 \(A_j \times c(i, j) \to FWT(A)_i\)。
那么 \(c(i, j)\) 只需满足 \(c(i, j) \cdot c(i, k) = c(i, j \oplus k)\)。
由于 \(\oplus\) 是位运算，所以可以按位分开考虑，那么只需知道
\(\begin{bmatrix} c(0, 0) & c(0, 1) \\ c(1, 0) & c(1, 1) \end{bmatrix}\)
（以及其逆矩阵）的值即可 \(\text{FWT}\)，这个矩阵称为位矩阵。
C
求 \(\displaystyle \left(\sum_{T\subseteq S}\sum_{i \in T} a_i\right)^p\)，等价于求所有 从 \(S\) 里可重复的选 \(p\) 个数（无序）求积 的和。
对于一个确定的集合 \(T\)，我们可以用指数生成函数解决选 \(p\) 个数（无序）求积的贡献和。
对 \(T\) 中每一个元素造指数生成函数 \(\displaystyle\hat G_i(x) = \sum_k a_i^k \cdot \frac{x^k}{k!} = e^{a_ix}\)，把 \(T\) 里所有元素的指数生成函数乘起来，得到 \(\displaystyle\hat G(x) = \prod_{i \in T} \hat G_i(x)\)，\([x^p]\hat G(x)\) 即为所求。
但是现在在外面又套了一层 \(S\)。
我们考虑普通生成函数，\(\displaystyle F(x) = \prod_i (1 + d_i x)\)。
其中 \([x^k] F(x)\) 的含义是所有选择 \(k\) 个元素的方案的权值和。
考虑在式子中其实 \(1\) 表示不选的贡献，\(d_i x\) 表示选的贡献。
那么直接把选一个元素会造成的贡献 \(\hat G_i(x)\) 放到选的贡献上，我们得到最终的式子：
\(\displaystyle\hat F(x) = \prod_i (1 + \hat G_i(x)) = \prod_i(1 + e^{a_ix})\)
带着 \(e^x\) 不好算，换元，令 \(t = e^x\)。
现在求 \(\displaystyle G(x) = \prod_i(1+x^{a_i})\)，直接分治 + NTT 求，它卡不住（bushi
求出 \(G(x)\) 的每一项记为 \(g_i\)，那么
\(\displaystyle\hat F(x) = \sum_i g_i e^{ix} = \sum_ig_i\sum_k \frac{i^kx^k}{k!} = \sum_k \frac{x^k}{k!} \sum_i g_i\cdot i^k\)。
把 \(k!\) 最后处理，那么剩下的是
\(\displaystyle \sum_kx^k \sum_{i} g_i \cdot i^k = \sum_ig_i\sum_{k}(ix)^k = \sum_{i}g_i \cdot \frac{1}{1 - ix}\)。
分治求并手动模拟分式加法（\(\frac{a}{b} + \frac{c}{d} = \frac{ad + bc}{bd}\)），最后给分母多项式求逆乘到分子。