AtCoder Regular Contest 106
A 106
枚举指数即可。
B Values
要求每个连通块内 \(\sum a=\sum b\)，这样一定可以得到答案。
C Solutions
比较简单的构造。
分 \(m\) 的值进行讨论。
-
\(m=0\)，直接输出 \([2i-1,2i]\) 即可。
-
\(m>0\)，在 \(m=0\) 的基础上，增加一个左端点为 \(1\)，右端点很大的区间，可以覆盖掉一些答案，例如得到区间 \([1,6],[2,3],[4,5]\) 此时按右端点排序的答案不变，按左端点排序的答案只会统计到 \([1,6]\)，因此在这个被覆盖的区间中不断增加新的小区间，则总共 \(k\) 个区间可以使按右端点排序的答案达到 \(k-1\)，而按左端点排序的答案始终为 \(1\)，因此 \(n\) 个区间最多达到 \(m=n-2\)，其余的值都不存在构造方案。
-
\(m<0\)，尝试模仿 \(m>0\) 的构造方法，由于一个区间右端点较小时无法覆盖掉其内部的较小区间，因此 \(m<0\) 实际是不合法的。更进一步地说，按照右端点排序的贪心算法实际上就是正解（感性证明是对于同一位置，其后增加的下一个区间一定右端点越小越优），因此不会存在其余做法得到答案更大的情况。
D Powers *
先简单推式子：
\[\begin{aligned} &\sum_{l=1}^{n-1}\sum_{r=l+1}^n (a_l+a_r)^x\\ =&\sum_{l=1}^{n-1}\sum_{r=l+1}^n \sum_{i=0}^x \dbinom{x}{i} a_l^i a_r^{x-i}\\ =&\sum_{l=1}^{n-1}x!\sum_{i=0}^x \dfrac{a_l^i}{i!} \dfrac{\sum_{r=l+1}^n a_r^{x-i}}{(x-i)!} \end{aligned}\]这样 NTT 的复杂度是 \(O(nk\log k)\)，无法通过。
考虑把 \(l<r\) 的限制去掉，求：
\[\sum_{l=1}^n\sum_{r=1}^n (a_l+a_r)^x \]这样可以化成：
\[x!\sum_{i=0}^x \dfrac{\sum_{l=1}^n a_l^i}{i!} \dfrac{\sum_{r=1}^n a_r^{x-i}}{(x-i)!} \]这样只需要卷一次，最后暴力去掉 \(l=r\) 的情况再除以 \(2\) 即可。
时间复杂度 \(O(nk+k^2)\)。
E Medals *
求满足条件最小转成二分。
判定等价于一个二分图匹配，\(nk\) 个左部点表示每个雇员的每个奖章，\(mid\) 个右部点表示每一天，则要求完美匹配。
根据 Hall 定理，我们需要判断每个左部点集 \(T\) 是否满足 \(|T|\le |N_G(T)|\)。容易发现对应雇员集合 \(S\) 相等的左部点集 \(T\) 的 \(N_G(T)\) 都同，而最大一个满足 \(|T|=k|S|\) 的点集满足条件则代表 \(S\) 对应的全部点集都满足，于是只需要判断 \(2^n\) 个集合。
式子 \(|T|\le |N_G(T)|\) 左侧值为 \(k\operatorname{popcount}(S)\)，右侧值等价于与当天到来的雇员集合与 \(S\) 有交的天数。
求有交自然补集转成求无交，那么就是求集合 \(U\backslash S\) 的所有子集之和，这一部分可以高维前缀和。
注意到每个左部点集连出的右部点数应当不低于 \(mid/2\)，因此当 \(mid\ge 2nk\) 时，一定有 \(|T|\le nk\le |N_G(T)|\)，因此二分区间为 \([nk,2nk]\)，总复杂是 \(O(nk^2+(nk+n2^n)\log (nk))\)。
F Figures
有标号无根树计数考虑 Prufer 序列，设 \(i\) 节点在 Prufer 序列中出现次数 \(p_i\)，则 \(0\le p_i<d_i\)，每个本质不同的序列 \(p\) 对答案的贡献是：
\[\dbinom{n-2}{p_1,p_2,\cdots,p_n}\prod_{i=1}^n \mathrm{A}_{p_i+1}^{d_i} \]写成 EGF 的形式：
\[F(x)=\sum_{i\ge 0}\dfrac{d!}{(d-i-1)!}\dfrac{x^i}{i!} \]答案要求 \((n-2)!\times [x^{n-2}]\prod F(x)\)，直接卷会超时。
思考如何写成封闭形式，发现系数与组合数比较类似，可以改写成以下两种：
\[F(x)=\sum_{i\ge 0} d\dbinom{d-1}{i}x^i=\sum_{i\ge 0} (i+1)\dbinom{d}{i+1}x^i \]前者比较好看，可以直接提出：
\[F(x)=d\sum_{i\ge 0} \dbinom{d-1}{i} x^i=d(1+x)^{d-1} \]因此卷积的结果：
\[\prod F(x)=\prod d\times (1+x)^{\sum (d-1)} \]答案即为：
\[(n-2)!\times \prod d\times \dbinom{\sum(d-1)}{n-2}=\prod d \left(\sum(d-1)\right)^{\underline{n-2}} \] 标签：nk,dbinom,乱写,ARC106,sum,端点,dfrac,prod,杂题 From： https://www.cnblogs.com/SoyTony/p/Problems_in_ARC_106.html