Codeforces Round 884

發表於 2023-07-12 更新於 2024-10-23 分類於 Codeforces ， Div1+2 Disqus：文章字數： 625 所需閱讀時間 ≈ 2 分鐘

G(线性代数,数学)H()

G - Tree Weights

n个点有边权(wi > 0权重未知)的树

给所有 i到i+1简单路径的长度di

求任意一个合法的边权方案,或者无方案

n 1e5

di [1,1e12]

256mb

根不影响点间距离和边长,因此直接把1选做根

首先可以 n log n 算所有 i与i+1的 lca

$u_i = lca(i,i+1)$

$path(i,i+1) = path(i,u_i)+path(i+1,u_i) = dep_i + dep_{i+1} - 2 dep_{u_i}$

所以可以得到一个 $(n-1)$行$(n+1)$列(其中一列是增广列) 矩阵

尝试求正解即可

它是一个系数矩阵非零项不多于 $4(n-1)$

然而并不会解稀疏矩阵, 还要把距离弄正

跟我想的一样也是先去掉树变成单纯的线性代数问题

然后神奇的来了,

因为求解的值域在整数(正整数), 系数也是整数, 考虑把线性方程的所有值, 放入 mod 2

那么在 mod 2的情况下, 上面的表达式就变成 $dep_i + dep_{i+1} \equiv path(i,i+1) \pmod 2$

那么因为1是根, $dep_1 \equiv 0 \pmod 2$, 从而 $dep_2,dep_3,\cdots,dep_n \pmod 2$都可以计算出了

所以上面的 $x_i+x_{i+1}-x_{lca(i,i+1)} = b_i$ 的最低位确定了

$x_i=2y_i+z_i(=0/1)$

$(2y_i+z_i) + (2y_{i+1}+z_{i+1}) - 2(2y_{lca(i,i+1)}+z_{lca(i,i+1)}) = b_i$

$y_i+y_{i+1} - 2y_{lca(i,i+1)} = \frac{b_i-z_i-z_{i+1}+2z_{lca(i,i+1)}}{2}$, 当这里始终可以整除,但这里为负数时就是无解

所以变成了子问题

注意到 $10^{12} \ge d \ge \max{edge}$

$dep \le n \max edge \le 10^{17}$

>>> 2**64  
18446744073709551616  
>>> 10**17  
100000000000000000

所以 $O(n \log (nd))$ 可做

最后再额外验证一下(吗?,或者验证高位剩余是0)

这样看的话, 如果有答案,只有唯一答案,虽然我拿到题目的时候就有感觉似乎并不能”任意有效解”

F1,F2

结论能猜对,证不了,还写了bug, 有个图形上的直觉

这个 mod 2可真神奇,我开始以为会有什么加速矩阵的运算方法,

哎 cf的题目就是, 这种学了题解会觉得真妙,amazing, 但是下次再见同样的技巧,不知道会是哪一年了

$1-\frac{n!k!\sum_{i=0}^{i\le k/2} \frac{1}{i!(n-k+i)!(k-2i)!2^i}}{n^k}$