A. 枚举,复杂度(O(log_3Nlog_5N)).
B. 判断每个连通块内部是否(a)的和与(b)的和相等,复杂度(O(N+M)).
C. Takahashi是正解,因此(M<0)无解. (M=0)只需要输出互不相交的线段.
如果(M>0),Aoki至少选一条线段,并且至少有Aoki的一条线段Takahashi不选,因此Takahashi的解至多为(N-1),故(Mge N-1)无解.
构造:(N-1)条互不相交线段以及覆盖其中最左边(M+1)条线段的线段.
D.$$sum_{L=1}{N-1}sum_{R=L+1}N(A_L+A_R)^X$$
[=dfrac12(-2^Xsum_{L=1}^NA_L^X+sum_{L=1}^Nsum_{R=1}^N(A_L+A_R)^X)
]
[=dfrac12(-2^Xsum_{L=1}^NA_L^X+sum_{i=0}^Xinom 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}^Xinom XiS(i)S(X-i)).)
(O(NK))预处理所有幂和(S)后(O(K^2))计算.
E.二分答案.构造二分图,一侧是员工,一侧是日期.用霍尔定理判断二分图是否可以匹配.用高维前缀和求出每个员工子集相邻的日期数量,日期数量必须大于或等于(K imes)员工数量.
复杂度(O(log(KN)(KN^2+2^NN)).)
F.考虑Prufer序列,(a_i)表示第(i)个点出现次数,考虑这些数在序列中的多重排列,每个点选取哪些接口,每个接口与哪个邻点相连,则答案为
[sum_{sum_{a_i}=n-2}(dfrac{n!}{prod a_i!}prodinom{d_i}{a_i+1}prod(a_i+1))
]
[=n!prod d_isum_{sum_{a_i}=n-2}prodinom{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(Nlog^2N)).