AtCoder-ABC318A Full Moon
暴力枚举判断。
提交记录：Submission - AtCoder
AtCoder-ABC318B Overlapping Sheets
暴力枚举判断。
提交记录：Submission - AtCoder
AtCoder-ABC318C Blue Spring
使用通票一定是用在最大的 \(kd\) 天，排序后枚举 \(k\) 即可。
提交记录：Submission - AtCoder
AtCoder-ABC318D General Weighted Max Matching
状压 DP。
提交记录：Submission - AtCoder
AtCoder-ABC318E Sandwiches
不妨在 \(a_i\) 处统计答案，对于每个值 \(k\)，将所有 \(a_i=k\) 拿出来，两个相邻位置\(x,y\) 之间的其他位置作为 \(j\)，贡献是左侧 \(a_i=k\) 的位置个数乘右侧个数。
提交记录：Submission - AtCoder
AtCoder-ABC318F Octopus
定义 \(d_i=|x_i-k|\)，等价于求出有多少 \(k\)，使排序后的 \(d\) 数组 \(d_i\le l_i\) 成立。
注意到 \(d\) 是绝对值函数，两个位置 \(i,j\) 的相对排名仅会在函数交点位置改变，因此本质不同的 \(d\) 数组只有 \(O(n^2)\) 个，对每个解若干不等式求出答案再取并。时间复杂度 \(O(n^3\log n)\)。
提交记录：Submission - AtCoder
AtCoder-ABC318G Typical Path Problem
问题和点双连通分量有关，建出圆方树发现就是问 \((A,B)\) 以及 \((C,B)\) 路径交是否存在除 \(B\) 以外的圆点。
提交记录：Submission - AtCoder
AtCoder-ABC318Ex Count Strong Test Cases
相当于 \(P_i\) 构成置换环。
考虑容斥，总方案数是 \((n!)^2\)，Alice 和 Bob 都正确当且仅当 \(P\) 是恒等置换，有 \(n!\) 种 \(Q\) 赋值的方案。
现在需要计算 Alice 正确的方案数，不难发现 Bob 正确的方案数和 Alice 相同，每个 Alice 正确的方案只需要把边权顺序完全调换就可以使 Bob 正确。
不妨设构成 \(k\) 个置换环，其中升序排序后环长为 \(l_i\)，对于每个 \(l\) 序列求解之后求和就是答案。
为置换环分配编号的方案是：
\[\dbinom{n}{l_1,l_2,\cdots,l_k}\dfrac{1}{k!}\prod_{i=1}^{k} (l_i-1)! \]这部分就是多重集排列数，除去环标号的方案，再乘上圆排列。
分配 \(Q\) 的方案数是：
\[n!\prod_{i=1}^{k} \dfrac{1}{l_i} \]容易发现每个环边权最小值和编号最小值对应的概率是环长的倒数。
上下两个式子乘起来整理，得到：
\[(n!)^2 \dfrac{1}{k!}\prod_{i=1}^{k} \dfrac{1}{l_i^2} \]设 \(F(x)=\sum_{i\ge 1} \frac{1}{i^2}x^i\)，结果就是 \((n!)^2 [x^n]\exp(F(x))\)。
最终答案是 \((n!)^2-2(n!)^2[x^n]\exp(F(x))+n!\)。
提交记录：Submission - AtCoder
标签：AtCoder,ABC318,Submission,记录,题解,Alice,提交,dfrac From： https://www.cnblogs.com/SoyTony/p/Solution_on_ABC318.html