Venus
CF1808E2&3 Minibuses on Venus
原题medium 原题hard 翻译 如果你不会CF1808E1的\(O(nK^3)\)做法,请点击这里 本题涉及:数据诈骗,这道题可以做到\(O(\log{n} + \log{K})\)的复杂度 我们发现对于所有数位的和\(S\),满足\(2x \equiv S (\mod K)\)的\(x\)的 ......
CF1808E1 Minibuses on Venus (easy version)
原题 翻译 一道数位\(dp\)题 记\(S = \sum_{i=1}^{n}{a_i}\),原题即要求是否存在\(i\)满足 \(S - a_i \equiv a_i (\mod K)\) 移项得\(S \equiv 2a_i (\mod K)\) 因此我们考虑枚举\(2a_i\)的值记作\(sm ......
题解 CF1808E【Minibuses on Venus】
problem 一个长为 $n$ 的序列,每一个数是 $[0,k)$ 的整数。说一个数列幸运,当且尽当 $\exists i$ 使得 $a_i\equiv(\sum_j a_j)-a_i\pmod k$,求方案数,$n\leq 10^{18},k\leq 2000$。 引理:若钦定数列的和为 $s$ ......
CF1808E3 - Minibuses on Venus
首先,我们考虑枚举所有的 $a_i$ 的和 $sum$。如果 $y$ 可以满足条件,那么 $y\equiv sum-y(\bmod k)$,也就是 $2y\equiv sum(\bmod k)$ 然后考虑有多少种可能的答案。我们发现,当 $k$ 是奇数的时候,$y$ 有唯一解。当 $k$ 是偶数的时 ......