题目传送门：Codeforces 1530
E Minimax
一道比较有意思的自己想出来的大力分类讨论的构造题。
首先只有一种字符，直接输出即可。
考虑\(f(S)=0\)如何构造，发现如果有某一个字符只出现了1次，将最小的那个放在第一个，剩下的依次输出即可。
若每个字符出现次数\(\ge 2\)，考虑第一个放最小的，剩下的考虑如果当前与第一个字符相同，那么下一个就一定不同，即形如aababacacada，由此得出次构造的条件是\(cnt_a-2\le n-cnt_a\)。
对于不满足上述条件的，若只有两个字符，则构造形如abbbaaa；否则，构造形如abaaacbbccdd，发现实际上\(f(S)\)是不会超过1的。
Submission
F Bingo
看上去就非常容斥。首先有很显然的一个容斥，将原题看作\(2n+2\)个限制，对这些限制容斥，即\(1-\text{钦定0个全为1}+\text{钦定1个}+\cdots\)，复杂度是\(\mathcal O(2^{2n}n)\)的，显然不能接受。
考虑先固定对角线和行的选择情况，得到一个概率\(res\)，在此基础上来考虑列的选择。记\(p_j\)表示强制选第\(j\)列还需要多少概率，发现如果强制选，就对答案\(\times (-p_j)\)，负号是因为要乘上容斥系数，否则就\(\times 1\)。所以对于一个状态的答案就是\(res\times \prod_{j=1}^{n} (1-p_j)\)。此时算出的\(ans\)是\(\text{恰好有0个全为1}\)的方案数，最终答案是\(1-ans\)。
Submission