E
题意:给定 A, X, M, 计算 (A0 + A1 + A2 + ... + AX-1) mod M (1 <= A, M <= 109, 1 <= X <= 1012)。
根据等比数列求和公式,(A0 + A1 + A2 + ... + AX-1) mod M = ((AX - 1) / (A - 1)) mod M。然而,此题如果用求和公式来求解显然是行不通的,下面会给出原因。
如果我们要用求和公式求解此题,首先,我们不能直接计算 ((AX - 1) mod M) / ((A - 1) mod M) mod M,因为对于正整数 a, b, p, "(a + b) mod p = ((a mod p) + (b mod p)) mod p" 这个等式是恒成立的,把 '+' 换成 '-' 或 '*' 也仍然恒成立,但如果是 '/',"恒成立" 这个说法就是错的。所以,对于取模运算下的除法,我们要想办法将其转化为乘法,我们需要找出一个正整数 x,使得在 mod p 的前提下,除以 b 就相当于乘以 x,即 (a / b) mod p = (a * x) mod p, 这个 x 称为 "b 在模 p 下的乘法逆元",记为 b-1(mod p)。b, x 满足 (b * x) mod p = 1 (这和 "倒数" 的概念可以说非常相似)。
求解方程 (b * x) mod p = 1,实际上就是要求出不定方程 bx + py = 1 的一组特解。根据贝祖定理,当且仅当 b, p 互质时才存在整数解。很遗憾,此题数据无法保证 (A - 1) 和 M 互质,所以用求和公式不可行。
解法一:举个例子,如果我们要计算 A0 + A1 + A2 + ... + A7,我们可以把它看成 (A0 + A1 + A2 + A3)、(A4 + A5 + A6 + A7) 之和,这二者又成倍数关系,所以原式就等于 (1 + A4) * (A0 + A1 + A2 + A3)。(1 + A4) 可以用快速幂计算得出,而 (A0 + A1 + A2 + A3) 又可以继续划分。如果原式最后一项不是 A7 而是 A8 ,项数是奇数怎么办?用快速幂单独计算 A8 再加上即可。这样一来,我们就得到了一个不断将原式一分为二的递归分治算法,时间复杂度为 O(logX)。
代码 (太菜了 20 多分钟才调出来 o(TヘTo) ):
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
LL ebs(const LL &a, const LL &b, const LL &m) { // 快速幂, 计算 (a ^ b) mod p
if (b == 0) return 1 % m;
LL tmp = ebs(a, b >> 1, m);
if (b & 1) return (tmp * tmp % m * a % m);
else return (tmp * tmp % m);
}
LL calc(const LL &a, const LL &x, const LL &m) { // 计算 a ^ 0 + a ^ 1 + ... + a ^ (x - 1)
if (x == 1) return 1 % m; // 递归边界, x == 1 表示只有一项, 无法继续划分
LL tmp = (1 + ebs(a, x >> 1, m)) * calc(a, x >> 1, m) % m;
if (x & 1) return ((tmp + ebs(a, x - 1, m)) % m); // 若 x 为奇数则单独计算 a ^ (x - 1), 再把它加上
else return tmp;
}
int main(void) {
LL a, x, m;
cin >> a >> x >> m;
cout << calc(a, x, m) << '\n';
return 0;
}
这里的的 "快速幂" 是递归实现的,实际上非递归也可以,如下:
long long pow_mod(long long a, long long b, long long p) {
assert(p != 0);
long long res = 1 % p;
for (; b; b >>= 1) {
if (b & 1) res = res * a % p;
a = a * a % p;
}
return res;
}
解法二:矩阵乘法加速递推
看了官方题解才知道这题还可以用矩阵,感觉上面那个解法明显更容易想到。时间复杂度同样为 O(logX)。
其中 Bi = A0 + A1 + ... + Ai, 不妨令 B0 = 0,显然 Bi = Bi-1 * A + 1。Bx 即为所求的答案。初始化矩阵 state = (B0, 1), 用 "矩阵快速幂" 计算出上式中 2 * 2 矩阵的 X 次方,再令 state 右乘之,即可得出答案。
代码:
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
LL a, x, m;
cin >> a >> x >> m;
LL state[1][2] = {{0, 1}}; // 状态矩阵 state
LL trans[2][2] = {{a, 0}, {1, 1}}; // 转移矩阵 trans
LL mat[2][2] = {{1, 0}, {0, 1}}; // 矩阵 mat 用来参与计算 trans 的 x 次方, 先初始化为单位矩阵
LL tmp[2][2] = {{0, 0}, {0, 0}}; // 矩阵 tmp 用于临时保存每次进行矩阵乘法的结果
auto clear_tmp = [&]() -> void { // 该 lambda 表达式用于将 tmp 归零
for (int i = 0; i < 2; ++i)
for (int j = 0; j < 2; ++j) tmp[i][j] = 0;
return;
};
for (; x; x >>= 1) {
if (x & 1) {
// 令 mat 乘上 trans
clear_tmp();
for (int i = 0; i < 2; ++i)
for (int j = 0; j < 2; ++j)
for (int k = 0; k < 2; ++k) tmp[i][j] = (mat[i][k] * trans[k][j] % m + tmp[i][j]) % m;
for (int i = 0; i < 2; ++i)
for (int j = 0; j < 2; ++j) mat[i][j] = tmp[i][j];
}
// 令 trans 自乘
clear_tmp();
for (int i = 0; i < 2; ++i)
for (int j = 0; j < 2; ++j)
for (int k = 0; k < 2; ++k) tmp[i][j] = (trans[i][k] * trans[k][j] % m + tmp[i][j]) % m;
for (int i = 0; i < 2; ++i)
for (int j = 0; j < 2; ++j) trans[i][j] = tmp[i][j];
}
// 最后一步, 令 state 乘上 mat
clear_tmp();
for (int i = 0; i < 1; ++i)
for (int j = 0; j < 2; ++j)
for (int k = 0; k < 2; ++k) tmp[i][j] = (state[i][k] * mat[k][j] % m + tmp[i][j]) % m;
state[0][0] = tmp[0][0], state[0][1] = tmp[0][1];
cout << state[0][0] << '\n';
return 0;
}
F
题意:给定正整数 N,计算有多少个不小于 2 的正整数 b,使得 N 在 b 进制下每一位均为 0 或 1。输出满足条件的 b 的个数。有 T 组测试数据。(1 <= T <= 1000, 1 <= N <= 1018)
解法:这题对我来说思维难度挺高的,比赛的时候完全没有思路。看了下官方题解才知道这道题有一个关键点:当 b > 1000 时,N 在 b 进制下不会超过 6 位数。所以我们可以先枚举 2~1000 看有多少个能满足条件。然后开一个 6 个元素的数组,每一个元素都只取 0 或 1 这两个值,就总共有 26 = 64 种情况。对于每一种情况,我们判断是否存在一个 b,使得 N 的 b 进制下的表示与这个数组表示的数完全相等,这个过程可以用二分查找来完成 (即可以查找最大的 b,使得 N 的 b 进制数大于等于该数组表示的数,然后判断是否能取等号)。
时间复杂度:O(T(999 + 64logN))
代码:
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
bool trial(LL n, LL base) { // 该函数用于判断 n 在 base 进制下是否全为 0 或 1
while (n) {
if (n % base > 1) return false;
n /= base;
}
return true;
}
vector<LL> generate(LL n, LL base) { // 该函数用于生成 n 的 base 进制, 返回一个存储六个 long long 的 vector 对象
vector<LL> ans(6, 0);
for (int i = 5; i >= 0; --i) {
ans[i] = n % base;
n /= base;
}
return ans;
}
vector<LL> num;
void dfs(LL &ans, LL n, int step) {
if (step == 6) { // 递归边界,此时我们已经得到了数组 num 的一种情况, 开始 "二分查找" 这一步骤
LL l = 1001, r = n, mid = 0;
while (l < r) {
mid = (l + r + 1) >> 1;
vector<LL> res = generate(n, mid); // 数组 res 表示 N 的 mid 进制
bool less = false; // 让数组 res 和 num 进行比较, 判断是 res < num 还是 res >= num
for (int i = 0; i < 6; ++i) {
if (res[i] < num[i]) {
less = true;
break;
}
}
if (less) r = mid - 1; // 如果 res < num, 说明 mid 大于我们要找的 b, b 一定在在 [l, mid - 1] 范围内
else l = mid; // 如果 res >= num, 则 mid 小于等于我们要找的 b, b 一定在在 [mid, r] 范围内
}
vector<LL> res = generate(n, l); // 此时的 l 即为我们要查找的最大的 b, 使得 N 的 b 进制数大于等于该数组表示的数
bool equal = true; // 最后判断是否可以取等号
for (int i = 0; i < 6; ++i) {
if (res[i] != num[i]) {
equal = false;
break;
}
}
if (equal) ++ans;
return;
}
num[step] = 1;
dfs(ans, n, step + 1);
num[step] = 0;
dfs(ans, n, step + 1);
return;
}
void solve(void) {
LL n, ans = 0;
cin >> n;
for (LL i = 2; i <= min(1000LL, n); ++i) // 枚举 2 ~ 1000
if (trial(n, i)) ++ans;
if (n > 1000) {
num.assign(6, 0); // 先将数组 num 赋值为 6 个 0
dfs(ans, n, 0); // 然后递归枚举每一种情况
}
cout << ans << '\n';
return;
}
int main(void) {
int t = 1;
cin >> t;
while (t--) solve();
return 0;
}
G
题意:给定有 N 个元素的数组 A, Q 个询问, 每次询问指定一个区间 [l, r], 问在 Al, Al+1, ..., Ar 这 (r - l + 1) 个数中有多少个不同的三元组 (i, j, k) 满足 Ai = Aj = Ak。
解法:这道题是莫队算法的模板题,这个算法我刚接触不久,还不太懂它为什么能把时间复杂度降到 O(n√n) ( 还望大佬们能指点指点 ( •̀ ω •́ )✧ )。大概意思就是,这道题,如果我们已经知道了一个区间 [l, r] 的答案,那么对于[l+1,r], [l, r - 1], [l - 1, r], [l, r + 1] 这四个区间,我们也可以用 O(1) 的时间得出答案。定义两个变量 l, r 用于表示区间 [l, r] 的左右边界,如果我们已经知道了第 i 个询问,即 [li, ri] 的答案,那么对于下一个提问,只要一步一步地移动 l 和 r,直至 l = li+1, r = ri+1 就可以得出下一个提问的答案。用分块的思想对提问进行合理的排序,可以有效地降低时间复杂度。
代码:
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int a[200005];
int st[500], en[500];
int bel[200005];
LL cnt[200005];
LL ans[200005], cur;
LL C3(const LL &n) {
if (n < 3) return 0LL;
return n * (n - 1) / 2LL * (n - 2) / 3LL;
}
void add(const int &p) {
cur -= C3((LL)cnt[a[p]]);
++cnt[a[p]];
cur += C3((LL)cnt[a[p]]);
return;
}
void del(const int &p) {
cur -= C3((LL)cnt[a[p]]);
--cnt[a[p]];
cur += C3((LL)cnt[a[p]]);
return;
}
struct Query {
int id;
int l;
int r;
bool operator<(const Query &a) const {
if (bel[l] != bel[a.l]) return l < a.l;
return (bel[l] & 1) ? r < a.r : r > a.r;
}
} q[200005];
int main(void) {
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; ++i) cin >> a[i];
for (int i = 1; i <= m; ++i) {
q[i].id = i;
cin >> q[i].l >> q[i].r;
}
// 分块
int sq = sqrt(n);
for (int i = 1; i <= sq; ++i) {
st[i] = sq * (i - 1) + 1;
en[i] = sq * i;
}
if (en[sq] < n) {
++sq;
st[sq] = en[sq - 1] + 1;
en[sq] = n;
}
for (int i = 1; i <= sq; ++i) {
for (int j = st[i]; j <= en[i]; ++j) bel[j] = i;
}
// 将询问进行排序
sort(q + 1, q + m + 1);
int l = q[1].l, r = q[1].r;
for (int i = l; i <= r; ++i) add(i);
ans[q[1].id] = cur;
for (int i = 2; i <= m; ++i) {
while (l > q[i].l) add(--l);
while (r < q[i].r) add(++r);
while (l < q[i].l) del(l++);
while (r > q[i].r) del(r--);
ans[q[i].id] = cur;
}
for (int i = 1; i <= m; ++i) cout << ans[i] << '\n';
return 0;
}
有不足的地方欢迎指出啊 (。・∀・)ノ
- Beginner AtCoder Contest 293 E-Gbeginner atcoder contest 293 contest programming beginner atcoder beginner atcoder contest 296 beginner atcoder contest 295 beginner atcoder contest abcde beginner atcoder contest 335 beginner atcoder contest 332 beginner atcoder contest 328 beginner atcoder contest 315 beginner atcoder contest 334