闲着的时候 vp 的一场 abc,vp 完之后发现自己居然 FG 都会/fad
为什么这场 abc 我没打/fn/fn/fn
ABC222E Red and Blue Tree
首先我们对每个 \(1\le i<n\),将 \(A_i\to A_{i+1}\) 中间的这些边的边权都加一。
设最后的边权序列为 \(x_{1\cdots n-1}\),把红边看做系数 \(c_i=+1\),蓝边看做系数 \(c_i=-1\),那么只需要最后所有 \(\sum x_ic_i=K\)。
\(f(i,j)\) 表示前 \(i\) 个数和为 \(j\) 的方案数,转移枚举最后一个填 \(+1\) 还是 \(-1\) 随便做。
注意 \(j\) 可以是负数,因此需要平移一波值域。
边权之和最大可以是 \(O(nm)\),因此总的时间复杂度为 \(O(n^2m)\)。
ABC222F Expensive Expense
一开始想的是 dp,然后发现我好像不太会写 up-down tree dp......
突然发现好像可以点分治:先把根节点 \(\text{rt}\) 子树内所有节点 \(u\) 的 \(\text{dist}(u)+D_u\) 扔进一个 multiset
,然后处理一棵子树的时候就把这棵子树内的点都从 multiset
里扔掉,不断更新答案,最后再扔进去。
时间复杂度 \(O(n\log ^2n)\),最慢的点跑了 \(\text{1886ms}\)(限时是 \(\text{4s}\)),海星。
ABC222G 222
套路题。
注意到 \(x\) 个 \(2\) 连起来其实就是 \(\dfrac{2}{9}(10^x-1)\)。
那么我们就只需要找一个最小的 \(x\) 使得 \(9K\mid 2(10^x-1)\)。
如果 \(2\mid K\),那么相当于 \(\left.\dfrac{9K}{2}\right|10^x-1\);如果 \(2\nmid K\),那么就是 \(9K\mid 10^x-1\)。
总之,不论如何,我们都可以将其转化为
\[10^x\equiv1\quad(\bmod N) \]其中 \(N=\dfrac{9K}{2}\) 或 \(9K\).
这个实际上就是 \(\bmod N\) 意义下 \(10\) 的阶,即 \(\text{ord}_{N}(10)\)。那么:
- 如果 \(\gcd(10,N)>1\),则 \(\text{ord}_{N}(10)\) 不存在,答案为 \(-1\)。
- 否则,\(\text{ord}_{N}(10)\) 必然为 \(\varphi(N)\) 的约数,枚举其约数并验证即可。
时间复杂度 \(O(T\sqrt{K}\log K)\),\(\log\) 来自快速幂。