1467
LY1467 [ 20231113 NOIP 模拟赛 T3 ] Remember11
题意 给定 \(n\) 个数,求将她们收尾拼接形成 \(11\) 的倍数的方案数。 Sol 数数题。 众所周知,是 \(11\) 的倍数意味着将该数错位相减 \(mod 11 = 0\)。 注意到偶数位数的数与奇数位数的数的贡献是不同的。 考虑将她们分开计算,然后合并。 设 \(f_{ijk}\) ......
CF1467E Distinctive Roots in a Tree
突然发现深究一些树上问题还是挺有意思的哈。 显然对于同一种权值的任意两个结点,其两端的部分都是不合法的。 维护两个标记表示子树内均不合法与子树外均不合法即可。但相同权值的点对数量是 \(O(n^2)\) 的,我们要优化这个过程。 发现很多点对都是无用的。DFS 下去,遇到一个 \(x\) 权值的结点 ......