2023.02.28琐记
追求真理之人
不可以心怀傲慢
不可以去嘲笑那些无法用科学解释的事物
不可以去回避这个世界的美丽
有的人仍在演着发病
有的人终会一笑了之
2023.02.28（1）
T1 tonight
读题困难。憨憨拓扑。
具体地，建出正反图，正图先找环把环上点打标记，再跑一边反图把所有让波特爆炸的点打标记。
如果被打标记中有初始为 \(0\) 的就寄了。
最后将未被标记的点做一次拓扑。
为什么这样是对的？如果拓扑到的当前点为 \(0\)，那肯定给它翻了。否则，不要去想可以简化步骤之类的，你如果给它翻过来之后它自己又怎么办？所以不要多想憨憨拓扑就完事了。
写的时候发现原图不用建，实际要建一张反图和一张原图的子图（即去除被标记点的图），因为反图也可以找环。
T2 nineoclock
在一个 \(n\) 个点的无向完全图上有 \(m\) 条边必选，求满足条件的排列数。
容易发现这个子图是由若干个环构成。
首先根据必选边建出一个新图，如果新图上的点中有度数大于 \(2\) 的，那么答案为 \(0\)。注意自环对单点的度数贡献为 \(2\)。
那么新图只可能由一些点，环或链组成。
对于环比较好算，只有正反向 \(2\) 种方案。注意只有环长大于 \(2\) 的才有正反不同贡献。
单点，单边，多边链各有不同，它们之间可以自己形成环，也可以进行拼接。方便表达以下统称为链。
注意相同长度的链并不一样。
考虑 \(n, m \le 2000\)。
考虑最终会形成的 “有效“ 环数 \(cnt\)，即大小大于 \(2\) 的环。
一个子图的贡献为 \(2^{cnt}\)，考虑枚举 \(cnt\)。
注意只关心属于三种类型中的哪一种，因此可以简化为已知三种链的数量然后计算。
这就不用考虑枚举每一条链了。
已知原有多边环 \(o\) 个，单点有 \(x\) 个，单边有 \(y\) 个，多边链有 \(z\) 个，最终形成多边环 \(cnt\) 个，求方案数。
这个要求 \(O(\log{n})\) 甚至 \(O(1)\)。
以下是补题了
方向稍偏。如果先考虑定向，然后链就可以缩成点考虑，然后再来拼接，要想到这一步的方案数就是缩点后总点数的排列数。
不考虑单边的情况，则方案数即为 \(2^{缩点数}\times 总点数!\)
然后容斥掉单边自成一体的情况。捏麻麻滴这么简单的容斥，sad:(
T3
感觉 \(300\) 确实是应该的了sadsadsadsadsad
这个调整为包含或不交的套路还是要注意一下的
标签：琐记,标记,拓扑,28,cnt,多边,2023.02 From： https://www.cnblogs.com/Schucking-Sattin/p/17165681.html