[补题记录] Atcoder Beginner Contest 293（E）

URL：https://atcoder.jp/contests/abc293

目录

E

Problem/题意

Thought/思路

Code/代码

---

E

Problem/题意

给出 A、X、M，求 。

Thought/思路

一开始想等比数列求和，但是 m 不保证是质数，所以不能用。

假设 dp[x] 表示，前 x 个数求和的值。

• 当 x 为偶数时：dp[x] = dp[x / 2] + dp[x / 2] * ksm(a, x / 2)
• 当 x 为奇数时：dp[x] = 1 + a * dp[x - 1]

Code/代码

不用记忆化也能过。

#include "bits/stdc++.h"#define int long longint a, x, m;
std::map <int, int> mp; // mp[x]：x 个数相加int ksm(int a, int b) {int res = 1;while (b > 0) {if (b & 1) res = res * a % m;b /= 2;a = a * a % m;}return res % m;
}int dfs(int x) {if (x == 1) return 1;if (x & 1) {mp[x - 1] = dfs(x - 1) % m;return (1 + a * mp[x - 1] % m) % m;} else {mp[x / 2] = dfs(x / 2) % m;return (mp[x / 2] + mp[x / 2] * ksm(a, x / 2) % m) % m;}
}signed main() {std::cin >> a >> x >> m;std::cout << dfs(x) % m;
}