Qoj 17472
记录一下 \(p\) 矩阵随机怎么做。
这个题方程类似于 \(\displaystyle F_i * P_{i,j} = I + x^{\{i\}} F_{j}\)，直接解方程需要同时处理 \(O(n2^n)\) 个未知数，显然不可接受。
考虑两边进行 \(\rm FWT\)，这样就能把每一位独立开。
具体地，这个题的方程是：
\[F_{S,i} = 1 + \sum_j p_{i,j} F_{S\Delta i,j}
\]
但是 \(S=\varnothing\) 有 corner，设 \(v_i = 1 + \sum_j p_{i,j}F_{\{i\},j}\)，则有
\[F_{\varnothing,i} = 1 + \left(\sum_j p_{i,j} F_{\{i\},j}\right) - v_i
\]
写成向量形式
\[F_i = \mathbf{1} + \left(\sum_j p_{i,j} \cdot F_j x^{\{i\}}\right) - v_i x^\varnothing
\]
两边 \(\rm FWT\) 即可得到
\[\hat F_{S,i} = 2^n[S = \varnothing] + \left(\sum_j p_{i,j} \cdot \hat F_{S,j} (-1)^{[i \in S]}\right) - v_i
\]
也就是每一位就独立了。我们对每一位分别解方程，可以得到 \(\hat F_{S,i} = \sum_{j}a_j x_j + b\)。但是 \(S=\varnothing\) 是解不出来的，所以再凑几个方程。
发现 \(\sum_{S} \hat F_{S,i} = 2^n F_{\varnothing,i} = 0\)，也就是 \(\hat F_{\varnothing,i} = - \sum_{S \neq \varnothing} \hat F_{S,i}\)。所以对所有非空的 \(F_{S,i}\) 解出来之后代入 \(S=\varnothing\) 的方程即可。
复杂度 \(O(2^nn^3)\)。