A. 枚举,复杂度\(O(\log_3N\log_5N)\).
B. 判断每个连通块内部是否\(a\)的和与\(b\)的和相等,复杂度\(O(N+M)\).
C. Takahashi是正解,因此\(M<0\)无解. \(M=0\)只需要输出互不相交的线段.
如果\(M>0\),Aoki至少选一条线段,并且至少有Aoki的一条线段Takahashi不选,因此Takahashi的解至多为\(N-1\),故\(M\ge N-1\)无解.
构造:\(N-1\)条互不相交线段以及覆盖其中最左边\(M+1\)条线段的线段.
D.$$\sum_{L=1}^{N-1}\sum_{R=L+1}^N(A_L+A_R)^X$$
记\(S(X)=\sum_{L=1}^NA_L^X\),则原式\(=\dfrac12(-2^XS(X)+\sum_{i=0}^X\binom XiS(i)S(X-i)).\)
\(O(NK)\)预处理所有幂和\(S\)后\(O(K^2)\)计算.
E.二分答案.构造二分图,一侧是员工,一侧是日期.用霍尔定理判断二分图是否可以匹配.用高维前缀和求出每个员工子集相邻的日期数量,日期数量必须大于或等于\(K\times\)员工数量.
复杂度\(O(\log(KN)(KN^2+2^NN)).\)
F.考虑Prufer序列,\(a_i\)表示第\(i\)个点出现次数,考虑这些数在序列中的多重排列,每个点选取哪些接口,每个接口与哪个邻点相连,则答案为
其中\([x^n](f(x))\)表示\(f(x)\)的\(n\)次系数.使用多项式快速幂(多项式对数+多项式指数)即可,复杂度\(O(N\log^2N)\).
AtCoder Regular Contest 106 题解
原文：https://www.cnblogs.com/Heltion/p/13871301.html