Solution Set -「LOCAL」冲刺省选 Round XXVIII
\(\mathscr{Summary}\)
??A 题显然是图论模型嘛……但是卡得太久了，B 题 C 题都不好骗，裂开 qwq。
??感觉时间安排上不尽合理，如果 B C 简单一点我这个就要挂打分了。可以尝试一下先打暴力再想正解。
\(\mathscr{Solution}\)
\(\mathscr{A}-\) 我
??给定字符串 \(S\) 以及 \(m\) 种变换，第 \(i\) 种将 \(S\) 中所有为 \(s_i\) 的字符替换为 \(t_i\)。求任意顺序将每种变换进行至少一次后，\(S\) 含有字符种类的最大值。
??多测，\(T\le100\)，\(|\Sigma|=62\)，\(m\le62\times61\)。
??字符当作点，替换操作当作有向边。令在 \(S\) 中存在的字符对应的点为黑色，否则为白色。注意到一个 SCC 内若有白点，那么这个 SCC 内的操作都可以执行而不减少黑点数量。那么缩点，对于全黑的 SCC，若其中的点需要被转移，那么强行踢出来一个黑点，让它自己找容身之所，得到一个有 \(1\) 个白点的 SCC；对于有 \(k\) 个白点的 SCC，它能容纳 \(k\) 个无家可归的黑点，DAG 上跑个最大流看几个被踢出来的黑点最终消失了即可。
??复杂度 \(\mathcal O(T\operatorname{Dinic}(|\Sigma|,m))\)。
\(\mathscr{B}-\) 想不出
??给定平面上 \(n\) 个点 \(p_{1..n}=(x_{1..n},y_{1..n})\)，现可以以每个点为端点，沿 \(-\frac{\pi}{3}\) 或者 \(-\frac{2\pi}{3}\) 的幅角方向引射线一条（哇，定语后置），求能得到的有限平面区域的最大数量。
??\(n\le2\times10^3\)。
??给空间整个线性变换，让每个点引的射线向右或者向上，注意 \(\tan\) 的非有理数性保证了没有两点共横坐标或纵坐标。
??欧拉定理知，对于连通平面图，\(|F_{\text{limited}}|=|E|-|V|+1\)，设射线交点集为 \(I\)，那么 \(|E|=2|I|\)，\(|V|=n_0+|I|\)，所以 \(|F_{\text{limited}}|=2|I|-n_0+1\)，而 \(\sum n_0=n\)，故我们只需要最大化 \(|I|\) 的总和。
??发现若两个点引的射线可能相交，则它们引出不相交且不平行的射线是一定不优的，推广这一结论，分析一下（嗯，我觉得我能证但我懒得想了 qwq），可知：每个点会向右引射线，当且仅当其右下方点数大于左上方数。
??BIT 模拟一下这些流程即可。复杂度 \(\mathcal O(n\log n)\)。
\(\mathscr{C}-\) 题目名称
??令 \(U=\bigcup_{i=1}^n[l_i,r_i]\cap\mathbb N\)，其中 \([l_i,r_i]\) 两两不交，求 \(\sum_{\{a,b,c,d\}\subseteq U}[a+b+c+d=s]\)。答案对 \(998244353\) 取模。
??\(n\le800\)，\(s\le8\times10^8\)。
??\(U\) 里选一个数的 GF：
\[F(x)=\sum_{i=1}^n\frac{x^{l_i}-x^{r_i+1}}{1-x}. \]想想怎么求答案的 GF。
??法一?集合元素具有互异性，我们暴力讨论 \(\{a,b,c,d\}\) 的相等关系，容斥：
- \(a,b,c,d\)（都不等）：容斥系数 \(1\times\) 自身方案 \(1F(x^4)\)。
- \(a=b,c,d\)：容斥系数 \(-1\times\) 自身方案 \(6F^2(x)F(x^2)\)。
- \(a=b,c=d\)：容斥系数：\((-1+1\times 2)\times\) 自身方案 \(1F^2(x^2)\)。
- \(a=b=c,d\)：容斥系数：\((-1+1\times 2)\times\) 自身方案 \(4F(x)F(x^3)\)。
- \(a=b=c=d\)：容斥系数 \((-1+1\times6-1\times3-2\times4)\times\) 自身方案 \(1F(x^4)\)。
综上，设答案的 GF 为 \(R(x)\)，则
\[R(x)=\frac{1}{4!}\left(F^4(x)-6F^2(x)F(x^2)+3F^2(x^2)+8F(x^3)F(x)-6F(x^4)\right). \]??法二?当然，如果你不愿意讨论……设选出 \(k\) 阶子集的 GF 为 \(R_k(x)\)，那么
\[\begin{aligned} R_k(x) &= [y^k]\prod_{u\in U}(1+x^uy)\\ &= (-1)^k[y^k]\prod_{u\in U}(1-x^uy)\\ &= (-1)^k[y^k]\exp\sum_{u\in U}\ln(1-x^uy)\\ &= (-1)^k[y^k]\exp-\sum_{i>0}\sum_{u\in U}\frac{x^{ui}y^i}{i}\\ &= (-1)^k[y^k]\exp-\sum_{i>0}\frac{y^iF(x^i)}{i}\\ &= (-1)^k[y^k]\prod_{i>0}\exp-\frac{y^iF(x^i)}{i}. \end{aligned} \]令 \(k=4\)，手算一下后面的 \(\exp\)，能够得到一样的 \(R(x)\)。
??法三？?呃……还有一个奇怪的东西。
\["\binom{F}{4}"=\frac{1}{4!}F(F-\text E)(F-2\text E)(F-3\text E). \]怎么你妈数学公式里整个引号。其中 \(\binom{F}{4}\) 即“在 \(F\) 中选四项的 GF”，\(\text E\) 是个算子，貌似具有比较优雅的性质……坐等 crashed 科普。UPD: 哦，上帝！我得和你打赌，她和她的文字肯定给你沐浴圣光的快慰！
??令 \(F(x)=(1-x)^{-1}G(x)\)，后面三项中，\(G(x),G(x^2)\) 等东西卷起来只有 \(\mathcal O(n^2)\) 项系数非 \(0\)，暴力做。对于前两项，考虑暴力求一半，然后在另一半里快速算对应系数：
??对于第一项：\(F^4(x)=G^2(x)\cdot(1-x)^{-4}G^2(x)\)，枚举 \(G^2(x)\) 里取的 \(x^{s-k}\)，那么后面部分有
\[\begin{aligned} \lbrack x^k\rbrack(1-x)^{-4}G^2(x) &= \sum_{i\le k}[x^i]G^2(x)\cdot\binom{k-i+3}{3}\\ &= \frac{1}{6}\sum_{i\le k}[x^i]G^2(x)(k-i+3)(k-i+2)(k-i+1)\\ &= \frac{1}{6}k^3\sum_{i\le k}[x^i]G^2(x)+\frac{1}{6}k^2\sum_{i\le k}(-3i+6)[x^i]G^2(x)\\ &~~~~+\frac{1}{6}k\sum_{i\le k}( 3i^2-12i+11)[x^i]G^2(x)+\frac{1}{6}\sum_{i\le k}(-i^3+6i^2-11i+6)[x^i]G^2(x). \end{aligned} \]这是关于 \(k\) 的低次多项式，暴力预处理系数，二分统计一个前缀的系数和。
??第二项，\(F^2(x)F(x^2)=F(x^2)\cdot(1-x)^{-2}(1-x^2)^{-1}G^2(x)\)，类似地，
\[\begin{aligned} \lbrack x^k\rbrack (1-x)^{-2}(1-x^2)^{-1}G^2(x) &= \sum_{i\le k,~2\nmid (k-i)}\frac{(k-i+1)(k-i+3)}{4}[x^i]G^2(x)+\sum_{i\le k,2\mid (k-i)}\frac{(k-i+2)^2}{4}[x^i]G^2(x)\\ &= \frac{1}{4}k^2\sum_{i\le k}[x^i]G^2(x)+\frac{1}{4}k\sum_{i\le k}(4-2i)[x^i]G^2(x)\\ &~~~~+\frac{1}{4}\sum_{i\le k}(i^2-4i+3)[x^i]G^2(x)+\frac{1}{4}\sum_{i\le k,~2\mid (k-i)}[x^i]G^2(x). \end{aligned} \]注意到 \([x^{s-k}]F(x^2)\neq 0\Rightarrow 2\mid(s-k)\)，所以最后和式里 \(2\mid (k-i)\) 中，\(i\) 与 \(s\) 同余才需要计入贡献，并不需要分类讨论奇偶性。
??复杂度 \(\mathcal O(n^2\log n)\)，瓶颈在于排序和二分指数位置。