\(2023.10.30-2023.11.1\)
\(\color{blueviolet}{AT\_abc285\_g}\)
神秘题。
网络流是显著的，建边方式如下：
- 所有边容量都为 \(1\)。
- 每个点拆为入点和出点，\(S\) 向入点连边，出点向 \(T\) 连边。
1的入点向出点连边。2的出点向四联通的2或?的入点连边?当做上两个处理。
考虑到唯一一种使得其不可行的构造是出现奇环，但网格显著并无奇环。
\(\color{blueviolet}{CF1530F}\)
此题是神秘题。
考虑反着做，将至少有一行或一列或一条对角线全为 \(1\) 概率转换为所有行列对角线都至少有一个 \(0\)。
先不考虑行与对角线，只考虑满足所有列都至少有一个 \(0\) 该怎么做，为了使得我们的不完全做法有扩展性，我们考虑使用容斥。
过程如下：
-
加上至少有 \(0\) 列全为 \(1\) 的概率。（对于至少有 \(x\) 列全为 \(1\) 的概率，可以理解为我们选定 \(x\) 列，使得其全为 \(1\)（概率相乘），其他列的 \(0/1\) 情况我们不考虑（概率为 \(1\)）。而选定的 \(x\) 列的所有情况概率要加和，比如我选定 \(1\) 列，那么情况总数有 \(n\) 种，这些情况的概率都要加和。）
-
减去至少有 \(2\) 列全为 \(1\) 的概率。
-
加上至少有 \(3\) 列全为 \(1\) 的概率。
-
以此类推。
这样容斥并不难理解，我们需要求的是所有列至少有一个 \(0\) 的情况，对于第一步加的概率显然是全情况的概率，我们减去其中有一列为 \(1\) 的概率，但此时对于两行为 \(1\) 的情况我们减了两遍。举个例子，对于 \(1,2\) 号列全为 \(1\) 的某种情况，我们选定 \(1\) 号列时和选定 \(2\) 好列时分别减去了一遍，所以要在接下来的运算中将其加回来，以此类推。
接下来考虑在这样计算列的贡献时计算行的贡献，首先每一行的贡献互不影响，考虑固定选定的列进行某一行的运算，我只要保证舍去行的全为 \(1\) 的概率即可。我们设 \(f_{i,j}\) 表示对于第 \(i\) 行，选定 \(j\) 状态列（\(j\) 是一个状压状态，这里选定其中的列就相当于在第 \(i\) 行中该位置一定为 \(1\)。），不考虑其他位置 \(0/1\) 状态的概率。这个东西显然是可以预处理的。
于是就有第 \(i\) 行在状态 \(j\) 下的贡献概率 \(g_{i, j} - g_{i, 2 ^ {n - 1}}\)，其中我们减掉的是此行全为 \(1\) 的状态，也就是上文说到舍去的部分
最后对角线与列的处理相同，枚举一下状态即可，使得一行与对角线交点的位置为 \(1\) 即可。
\(\color{blueviolet}{CF1530F}\)
此题是坏题，他卡你空间。
每一个元素有选或不选两种状态，并且有依赖项，元素的贡献有正负，数据范围不大，可以自然联系到最大权闭合子图，采用最小割模型。
建模方式如下：
- 对于一个正权点 \(u\)，连边 \(S \to u\)，容量为 \(b_i\)。
- 对于一个负权点 \(u\)，连边 \(u \to T\)，容量为 \(-b_i\)。
- 对于所有 \(i\)，对于其所有依赖的 \(j\) 连边，容量为正无穷。
但这样建边空间就爆炸了，考虑到值域很小，一个数不同约数个数不会很多。对于一个数 \(a_i\)，枚举其约数 \(x\)，对于每一个 \(x\) 只需要向最近的 \(x\) 建边即可，这样由于依赖关系的传递性不会出问题。
现在考虑最小割的意义，对于源点到正权点的一条边流满表示这个点我们舍弃掉了，对于负权点到汇点的边流满表示这个点我们被迫选择了，所以有答案 \(\left( \sum \limits _ {b_i > 0} b_i \right) - f\)，其中 \(f\) 为最小割。
\(\color{royalblue}{CF1517E}\)
思考发现最后的串只能是 C/P CCC PCPCPC PPP C/P 或者 PPPPP CCCCC 这种形式，大力分类讨论，注意细节即可。
\(\color{blueviolet}{CF1511F}\)
先建 Trie 树，设 \(f_{i, u, v}\) 到第 \(i\) 个字符，两个分割分别处在 \(u\) 节点与 \(v\) 节点的方案数。
暴力转移是简单的，数据范围提醒我们要用矩阵优化，对于一个状态（有序数对）\((u, v)\) 建立一个点，若状态 \((u, v)\) 可以向 \((u', v')\) 转移，则在代表两个状态的点之间连边。
特殊地，若 \(u'\) 是终止节点，则 \((u', v')\) 同时具有 \((0, v')\) 的转移，\(v'\) 也同理；若 \(u', v'\) 都是终止节点，状态 \((u', v')\) 同时具有 \((0, 0)\) 的转移。
所以对于上述情况，\((u, v)\) 也可以向 \((u', v')\) 的等价状态连一条边，于是我们得到了一个有向图，等价于让我们求长度为 \(m\) 的从 \((0, 0)\) 到 \((0, 0)\) 路径条数，但此时状态数是 \(1600\) 左右的，显然我们不能接受，考虑优化方式。
首先对于状态 \(u, v\) 它可能是不存在的，因为 \(u, v\) 在 Trie 树上的形态必然是祖先和子代的关系，状态数来到 \(320\) 左右，再考虑 \((u, v)\) 和 \((v, u)\) 在上述图中是对称的存在，考虑在矩阵中所成一个状态即可。
\(\color{limegreen}{CF1490G}\)
塞到 set 里乱搞即可。
标签：连边,概率,Log,2023.10,状态,color,对于,30,考虑 From： https://www.cnblogs.com/Eon-Sky/p/17802208.html