链接：https://codeforces.com/gym/104337
C
画个图看看，复杂度 \(O(1)\)。
C++ Code
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
cout << min(n, m) + (abs(n - m) + 1) / 2 << '\n';
return 0;
}
F
\(\text{manacher}\) 会在字符串两端和中间加字符，所以只看奇数位就行，\(a_{i}=1\) 就 \(\text{a}\) 变 \(\text{b}\)，\(\text{b}\) 变 \(\text{a}\)，复杂度 \(O(n)\)。
C++ Code
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<int> a(2 * n + 2);
for (int i = 0; i < 2 * n + 2; i++) {
cin >> a[i];
}
char c[] = {'a', 'b'};
string s = "a";
int j = 0;
for (int i = 3; i < 2 * n; i += 2) {
if (a[i] == 1) {
s += c[j ^= 1];
} else {
s += c[j];
}
}
cout << s << '\n';
return 0;
}
H
先考虑朴素，但是发现 \(deg_{i}\) 只有 \(\sqrt{2m}\) 种，复杂度 \(O(2m)\)。
C++ Code
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
constexpr int P = 998244353;
struct mint {
i64 x;
mint(const i64 &x) : x(x % P) {}
};
mint operator*(const mint &a, const mint &b) {
return a.x * b.x;
}
mint operator+(const mint &a, const mint &b) {
return a.x + b.x;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<int> deg(n);
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
u--, v--;
deg[u]++;
deg[v]++;
}
int mx = *max_element(deg.begin(), deg.end());
vector<int> cnt(mx + 1);
vector<int> f;
for (int i = 0; i < n; i++) {
if (!cnt[deg[i]]) {
f.push_back(deg[i]);
}
cnt[deg[i]]++;
}
mint ans = 0;
int N = f.size();
for (int i = 0; i < N; i++) {
for (int j = i + 1; j < N; j++) {
mint a = f[i] ^ f[j];
mint b = f[i] & f[j];
mint c = f[i] | f[j];
mint k = 1LL * cnt[f[i]] * cnt[f[j]];
ans = ans + a * b * c * k;
}
}
cout << ans.x << '\n';
return 0;
}
I
记 \(m=lcm(a_{1}, a_{2}, \cdots, a_{n})\)，题意抽象为，找最小的 \(t\)，使得 \(t(t +1)\) 为 \(2m\) 的倍数，用 \(\text{pollard rho}\) 对 \(m\) 质因子分解一下，\(t\) 和 \(t+1\) 互质，所以每种质因子的积只能其中一个的因子，直接枚举得到 \(a,b\)，可以子集枚举，也可以 \(\text{dfs}\)，最后问题转化为找 \(x,y\) 满足 \(by-ax=1\)，\(\text{exgcd}\) 搞一下，复杂度不会算。
C++ Code
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
using i128 = __int128;
i64 power(i64 a, i64 b, i64 m) {
i64 res = 1;
for (; b; b >>= 1, a = i128(a) * a % m) {
if (b & 1) {
res = i128(res) * a % m;
}
}
return res;
}
bool isprime(i64 p) {
if (p < 2) {
return 0;
}
i64 d = p - 1, r = 0;
while (!(d & 1)) {
r++;
d >>= 1;
}
int prime[] = {2, 3, 5, 7, 11, 13, 17, 19, 23};
for (auto a : prime) {
if (p == a) {
return true;
}
i64 x = power(a, d, p);
if (x == 1 || x == p - 1) {
continue;
}
for (int i = 0; i < r - 1; i++) {
x = i128(x) * x % p;
if (x == p - 1) {
break;
}
}
if (x != p - 1) {
return false;
}
}
return true;
}
mt19937 rng((unsigned int) chrono::steady_clock::now().time_since_epoch().count());
i64 pollard_rho(i64 x) {
i64 s = 0, t = 0;
i64 c = i64(rng()) % (x - 1) + 1;
i64 val = 1;
for (int goal = 1; ; goal <<= 1, s = t, val = 1) {
for (int step = 1; step <= goal; step++) {
t = (i128(t) * t + c) % x;
val = i128(val) * abs(t - s) % x;
if (step % 127 == 0) {
i64 g = gcd(val, x);
if (g > 1) {
return g;
}
}
}
i64 g = gcd(val, x);
if (g > 1) {
return g;
}
}
}
unordered_map<i64, int> getprimes(i64 x) {
unordered_map<i64, int> p;
function<void(i64)> get = [&](i64 x) {
if (x < 2) {
return;
}
if (isprime(x)) {
p[x]++;
return;
}
i64 mx = pollard_rho(x);
get(x / mx);
get(mx);
};
get(x);
return p;
}
i64 exgcd(i64 a, i64 b, i64 &x, i64 &y) {
if (!b) {
x = 1;
y = 0;
return a;
}
i64 d = exgcd(b, a % b, x, y);
i64 t = x;
x = y;
y = t - (a / b) * y;
return d;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<int> a(n);
i64 m = 1;
for (int i = 0; i < n; i++) {
cin >> a[i];
m = lcm(m, a[i]);
}
m = 2 * m;
auto p = getprimes(m);
vector<i64> f;
for (auto &[u, v] : p) {
i64 res = 1;
for (int i = 0; i < v; i++) {
res *= u;
}
f.push_back(res);
}
int N = f.size();
i64 ans = 9E18;
function<void(int, i64)> dfs = [&](int j, i64 a) {
if (j == N) {
i64 b = m / a;
i64 x = 0, y = 0;
i64 g = exgcd(a, b, x, y);
x = ((-x) % b + b) % b;
if (x == 0) {
x = b;
}
ans = min(ans, a * x);
return;
}
dfs(j + 1, a);
dfs(j + 1, a * f[j]);
};
dfs(0, 1);
cout << ans << '\n';
return 0;
}
J
前缀和，模拟一下，复杂度 \(O(n)\)。
C++ Code
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
vector<i64> sum(a.begin(), a.end());
partial_sum(sum.begin(), sum.end(), sum.begin());
if (sum[n - 1] < 0) {
cout << -1 << '\n';
return 0;
}
i64 ans = 0;
i64 cur = 0;
i64 mx = 0;
for (int i = 0; i < n; i++) {
cur += sum[i];
if (cur < 0) {
if (mx == 0) {
cout << -1 << '\n';
return 0;
}
i64 k = (-cur + mx - 1) / mx;
ans += k;
cur += k * mx;
}
mx = max(mx, sum[i]);
ans++;
}
cout << ans << '\n';
return 0;
}
K
投出 \(i\) 输的概率为 \((\frac{m-i}{m-1})^{n}\)。
C++ Code
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
constexpr int P = 998244353;
i64 power(i64 a, i64 b) {
i64 res = 1;
for (; b; b >>= 1, a = a * a % P) {
if (b & 1) {
res = res * a % P;
}
}
return res;
}
i64 inv(i64 x) {
return power(x, P - 2);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
i64 Inv = inv(power(m - 1, n));
for (int i = 1; i <= m; i++) {
cout << power(m - i, n) * Inv % P << " \n"[i == m];
}
return 0;
}
M
枚举那个 \(\text{1000}\) 块的，复杂度 \(O(x)\)。
C++ Code
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int x, y;
cin >> x >> y;
int N = 1E6;
for (int i = 0; i <= x; i++) {
int c = y - (i * 1000);
if (c % 2500 == 0) {
int j = c / 2500;
if (j <= x - i) {
cout << x - i - j << ' ' << i << ' ' << j << '\n';
return 0;
}
}
}
cout << -1 << '\n';
return 0;
}