由于各种各样的原因，本蒟蒻无法参加ARC 106的比赛，只能赛后看题。

A: 不能溢出(WA×2)，用__int128搞结果好多东西没有转型(WA×1)，把输入的 n n n前的 l o n g   l o n g long\ long long long误去掉了(WA×1)

B: 没有特判两条边在一个连通块内的情况，导致并查集的 m e r g e merge merge操作写挂(WA×2)

C: 没看到 l l l两两不同， r r r两两不同的要求(WA×1)，没看到 l i , r i ≤ 1 0 9 l_i,r_i≤10^9 li​,ri​≤109的条件(WA×1)，没特判 n = 1 n=1 n=1的情况(WA×1)

D: 式子推错，导致重查浪费时间。

菜成这个样子，估计蓝勾拿不到了吧/kel

Solution

A

略。

B

可以发现一个性质: 如果一个连通块内，节点的所有初始权值之和与目标权值之和相等，那么这个连通块一定能够达到要求，否则一定不行。

于是，我们使用并查集维护连通块内节点初始权值之和与节点目标值之和。最后，看一下是否所有连通块都满足要求。

注意 m e r g e merge merge的时候特判一下连接的两个节点已在一个连通块内的情况。

时间复杂度 O ( n l o g n ) O(nlogn) O(nlogn)。使用按秩合并并查集(启发式合并)可以优化到 O ( n ) O(n) O(n)，不过这并没有必要。

C

这是一道比较新颖的题套题。

首先，我们先看看题目中的那道题。毫无疑问，两人最终选定的区间都两两不相交，但是 T T T(Takahashi)的解法正确(能够得到最大值)， A A A(Aoki)的解法错误。

所以，我们先判断 m < 0 m<0 m<0的情况。根据上面两人解法的性质，显然应该输出 − 1 -1 −1。

然后，考虑如何构造。首先，我们先摆一个极大区间，左端点为 1 1 1，右端点为 1 0 9 10^9 109。此时， A A A只能选择一个区间。

然后，我们构造 m + 1 m+1 m+1个互不相交的小区间，让 T T T把这些区间选走。最后，对于剩下的 n − ( m − 2 ) n-(m-2) n−(m−2)个区间，我们随便放一些极大区间，凑满 n n n个区间。所以，如果 n − ( m − 2 ) ＜ 0 n-(m-2)＜0 n−(m−2)＜0即 m ≥ n − 1 m≥n-1 m≥n−1，要直接输出 − 1 -1 −1。

注意， l l l必须两两不同， r r r也必须两两不同。所有极大区间的右端点不能超过 1 0 9 10^9 109。

---

可是为啥还是 ⌊ \lfloor ⌊ WA ⌉ \rceil ⌉？

你看一下 n = 1 , m = 0 n=1, m=0 n=1,m=0的情况，你程序输出了 − 1 -1 −1；可以你是不是可以构造出一个满足要求的区间呢？

于是特判一下这个边界情况，就过了。

时间复杂度 O ( n ) O(n) O(n)。

D

一道使用二项式定理推式子的套路数学题。

∑ i = 1 n − 1 ∑ j = i + 1 n ( a i + a j ) x \sum_{i=1}^{n-1} \sum_{j=i+1}^n (a_i+a_j)^x ∑i=1n−1​∑j=i+1n​(ai​+aj​)x

= 1 2 [ ∑ i = 1 n ∑ j = 1 n ( A i + A j ) x − ∑ i = 1 n ( 2 a i ) x ] =\frac 1 2[\sum_{i=1}^n \sum_{j=1}^n (A_i+A_j)^x-\sum_{i=1}^n (2a_i)^x] =21​[∑i=1n​∑j=1n​(Ai​+Aj​)x−∑i=1n​(2ai​)x]

可以发现，对于一个 x x x，后面的 ∑ i = 1 n ( 2 a i ) x \sum_{i=1}^n (2a_i)^x ∑i=1n​(2ai​)x可以 O ( n ) O(n) O(n)去求，前面的 1 2 \frac 1 2 21​也好搞(最后乘上 2 2 2在模 998244353 998244353 998244353意义下的逆元即可)。关键在于中间的那个式子。

我们只保留中间的那个东西：

∑ i = 1 n ∑ j = 1 n ( A i + A j ) x \sum_{i=1}^n \sum_{j=1}^n (A_i+A_j)^x ∑i=1n​∑j=1n​(Ai​+Aj​)x
= ∑ i = 1 n ∑ j = 1 n ∑ k = 0 x C x k A i k A j x − k =\sum_{i=1}^n \sum_{j=1}^n \sum_{k=0}^x C_x^k A_i^k A_j^{x-k} =∑i=1n​∑j=1n​∑k=0x​Cxk​Aik​Ajx−k​(二项式定理展开)
= ∑ k = 0 x C x k ( ∑ i = 1 n A i k ) ( ∑ i = 1 n A i x − k ) =\sum_{k=0}^x C_x^k (\sum_{i=1}^n A_i^k)(\sum_{i=1}^n A_i^{x-k}) =∑k=0x​Cxk​(∑i=1n​Aik​)(∑i=1n​Aix−k​)

可以发现，此时我们可以分别用阶乘逆元预处理+ O ( 1 ) O(1) O(1)查询求出 C x k C_x^k Cxk​，单次在 O ( n l o g x ) O(nlogx) O(nlogx)的复杂度下求出 ∑ i = 1 n A i k \sum_{i=1}^n A_i^k ∑i=1n​Aik​与 ∑ i = 1 n A i x − k \sum_{i=1}^n A_i^{x-k} ∑i=1n​Aix−k​。

总时间复杂度 O ( n k l o g k ) O(nklogk) O(nklogk)。壮哉我大二项式定理！

花絮: 我这题代码的复杂度还是蛮高的，结果不卡常就轻松通过(还只有 1.1 s 1.1s 1.1s)…… A T AT AT的评测机太强啦！

E

大力网络流建图优化，不会。

F

多项式神仙题，不会。