1808E
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 ......
CF1808E3 题解
## 题意 [传送门](https://www.luogu.com.cn/problem/CF1808E3) 求有多少包含 $n$ 位数码的 $k$ 进制数,满足存在一位数等于其他 $n-1$ 位数的总和模 $k$。 $1\le n\le 10^{18},1\le k\le 2000$。 ## 题解 ......
题解 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$ 是偶数的时 ......