首页 > 其他 > 详细

AtCoder Regular Contest 106 题解

时间:2020-10-24 22:48:03      阅读:28      评论:0      收藏:0      [点我收藏+]

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$$

\[=\dfrac12(-2^X\sum_{L=1}^NA_L^X+\sum_{L=1}^N\sum_{R=1}^N(A_L+A_R)^X) \]

\[=\dfrac12(-2^X\sum_{L=1}^NA_L^X+\sum_{i=0}^X\binom Xi(\sum_{L=1}^NA_L^i)(\sum_{R=1}^NA_R^{X-i}). \]

\(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\)个点出现次数,考虑这些数在序列中的多重排列,每个点选取哪些接口,每个接口与哪个邻点相连,则答案为

\[\sum_{\sum_{a_i}=n-2}(\dfrac{n!}{\prod a_i!}\prod\binom{d_i}{a_i+1}\prod(a_i+1)) \]

\[=n!\prod d_i\sum_{\sum_{a_i}=n-2}\prod\binom{d_i-1}{a_i} \]

\[=n!\prod d_i[x^{n-2}]((1+x)^{\sum(d_i-1)}). \]

其中\([x^n](f(x))\)表示\(f(x)\)\(n\)次系数.使用多项式快速幂(多项式对数+多项式指数)即可,复杂度\(O(N\log^2N)\).

AtCoder Regular Contest 106 题解

原文:https://www.cnblogs.com/Heltion/p/13871301.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!