Competition link: Here
AB water question,
C – Sum of gcd of Tuples (Easy)
Question meaning: \(\sum_{a=1}^{K} \sum_{b=1}^{K} \sum_{c=1}^{K} g c d(a, b, c) \)
Data range: \(1\le K\le 200\)
Idea: Because \(k\) is relatively small, we can just run violence directly
int main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
ll n; cin >> n;
ll ans = 0;
for (int i = 1; i <= n; i + + )
for (int j = 1; j <= n; j + + )
for (int k = 1; k <= n; k + + )
ans + = __gcd(__gcd(i, j), k);
cout << ans;
}
D – RGB Triplets
Question meaning: Given a string S of length N, it only contains ‘R’, ‘B’, and ‘G’. Find how many triples \((i,j,k)(1\le i Data range: \(1\le N \le 4000\) Solution: First calculate the equation that satisfies \(_{i} \\ The total is obviously equal to \(num(R)*num(B)*num(G)\), and then enumerate the two endpoints to determine whether the third endpoint is different from the color of the two endpoints.
eq S_{j}, S_{i} \\
eq S_{k}, S_{j} \\
eq S_{k}\), After subtracting the number of \(j-i \\
eq k-j\).
const int N = 4e3 + 5;
int main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int n; string s;
cin >> n >> s;
int a = 0, b = 0, c = 0;
for (int i = 0; i < n; + + i) {
if (s[i] == 'R') a + = 1;
if (s[i] == 'G') b + = 1;
if (s[i] == 'B') c + = 1;
}
ll ans = 1ll * a * b * c;
for (int i = 0; i < n; i + + )
for (int j = i + 1; j < n; j + + ) {
if (s[i] == s[j]) continue;
if (2 * j - i < n & amp; & amp; s[i] != s[2 * j - i] & amp; & amp; s[j] != s[2 * j - i]) ans--;
}
cout << ans;
}
E – Sum of gcd of Tuples (Hard)
Question meaning: \(\sum_{a_{1}=1}^{K} \sum_{a_{2}=1}^{K} \ldots \sum_{a_{N}=1} ^{K} g c d\left(a_{1}, a_{2}, \ldots, a_{N}\right)(\bmod 1 \mathrm{e} 9 + 7)\)
Data range: \(2 \leq N \leq 10^{5}, 1 \leq K \leq 10^{5}\)
Idea 1: Mobius inverse evolution simplified
\[\begin{array}{l} A n s=\sum_{a_{1}=1}^{K} \sum_{a_{2}=1}^{K} \ldots \ sum_{a_{N}=1}^{K} g c d\left(a_{1}, a_{2}, \ldots, a_{N}\right) \ =\sum_{i =1}^{K} \sum_{a_{1}=1}^{K} \sum_{a_{2}=1}^{K} \ldots \sum_{a_{N}=1 }^{K} i\left[\operatorname{gcd}\left(a_{1}, a_{2}, \ldots, a_{N}\right)==i\right] \ \\ =\sum_{i=1}^{K} \sum_{a_{1}=1}^{\left\lfloor\frac{K}{i}\right\rfloor } \sum_{a_{2}=1}^{\left\lfloor\frac{K}{i}\right\rfloor} \ldots \sum_{a_{N}=1} ^{\left\lfloor\frac{K}{i}\right\rfloor} i\left[\operatorname{gcd}\left(a_{1}, a_{2}, \ \ldots, a_{N}\right)==1\right] \ =\sum_{i=1}^{K} \sum_{a_{1}=1}^{\ left\lfloor\frac{K}{i}\right\rfloor} \sum_{a_{2}=1}^{\left\lfloor\frac{K}{i}\ right\rfloor} \ldots \sum_{a_{N}=1}^{\left\lfloor\frac{K}{i}\right\rfloor} i \sum_{d= 1}^{\left\lfloor\frac{K}{i}\right\rfloor} \mu(d)\left\lfloor\frac{d}{a_{1}} \right\rfloor\left\lfloor\frac{d}{a_{2}}\right\rfloor \ldots\left\lfloor\frac{d}{a N}\ \right\rfloor \ =\sum_{i=1}^{K} i \sum_{d=1}^{\left\lfloor\frac{K}{\imath} \right\rfloor} \mu(d) \sum_{a_{1}=1}^{\left\lfloor\frac{K}{i d}\right\rfloor} \ sum_{a 2=1}^{\left\lfloor\frac{K}{i d}\right\rfloor} \ldots \sum_{a N=1}^{\left\ lfloor\frac{K}{i d}\right\rfloor} 1 \ =\sum_{i=1}^{K} i \sum_{d=1}^{\left\ \lfloor\frac{K}{i}\right\rfloor} \mu(d)\left\lfloor\frac{K}{i d}\right\rfloor^{N} \ \\ =\sum_{T=1}^{K}\left\lfloor\frac{K}{T}\right\rfloor^{N} \sum_{d \mid T } \mu(d) *\left\lfloor\frac{T}{d}\right\rfloor(T=i d) \ =\sum_{T=1}^{K }\left\lfloor\frac{K}{T}\right\rfloor^{N} \phi(T) \end{array} \]
Since \(K\) is not large, you can preprocess the Euler function and traverse it directly. If \(K\) is large, divide it into blocks and add Dujiao sieve (fog.
#include <bits/stdc + + .h>
using ll = long long;
using namespace std;
const int N = 1e5 + 5, MD = 1e9 + 7;
int pri[N], tot, phi[N];
bool p[N];
void init() {
p[1] = true, phi[1] = 1;
for (int i = 2; i < N; i + + ) {
if (!p[i]) pri[ + + tot] = i, phi[i] = i - 1;
for (int j = 1; j <= tot & amp; & amp; i * pri[j] < N; j + + ) {
p[i * pri[j]] = true;
if (i % pri[j] == 0) {
phi[i * pri[j]] = phi[i] * pri[j];
break;
} else phi[i * pri[j]] = phi[i] * (pri[j] - 1);
}
}
}
ll qpow(ll a, ll b) {
ll ans = 1;
for (; b; b >>= 1, a = a * a % MD) if (b & amp; 1) ans = ans * a % MD;
return ans;
}
void add(int & amp;x, int y) { x + = y; if (x >= MD) x -= MD;}
int main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
init();
int n, k, ans = 0;
cin >> n >> k;
for (int i = 1; i <= k; i + + )
add(ans, 1LL * qpow(k / i, n)*phi[i] % MD);
cout << ans;
}
Idea two:
Learned the official solution: Define \(f[i]\) to represent \(\gcd\) as the number of \(i\), the recursion relation: \(f[i ]=\left\lfloor\frac{K}{i}\right\rfloor^{N}-\sum_{j>i, i \mid j} f[j]_{\ circ}\)?
Just use a double loop. The sum of the complexity of the loops inside is a harmonic series, at the \(\log\) level.
const int N = 1e5 + 5, MD = 1e9 + 7;
int f[N];
ll qpow(ll a, ll b) {
ll ans = 1;
for (; b; b >>= 1, a = a * a % MD) if (b & amp; 1) ans = ans * a % MD;
return ans;
}
void add(int &x, int y) {
x + = y;
if (x >= MD) x -= MD;
if (x < 0) x + = MD;
}
int main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int n, k;
scanf("%d%d", & amp;n, & amp;k);
cin >> n >> k;
for (int i = k; i >= 1; i--) {
f[i] = qpow(k / i, n);
for (int j = 2 * i; j <= k; j + = i)
add(f[i], -f[j]);
}
int ans = 0;
for (int i = 1; i <= k; i + + )
add(ans, 1LL * f[i]*i % MD);
cout << ans;
}
F – Select Half
Question: Given a sequence \(A\) of length \(N\), you are asked to choose \(\left[\frac{N}{2}\right\rfloor\ ) number, and the subscripts are not adjacent to each other, maximize their sum.
Data range: \(2\le N\le 2\times 10^5\)
Solution: For the subscript of the selected number, \(B_{1}, B_{2} \ldots, B_{\left\lfloor\frac{N}{2}\right\rfloor} \), you can find\(\sum_{i=2}^{\left\lfloor\frac{N}{2}\right\rfloor} B_{i}-B_{i- 1}-2 \leq 2\)
Therefore, the definition \(f[i][j]\)? means selecting the number in \(1~i\) (the first \(i\) number must be selected), and there is a long and empty space in front. The maximum value of \(j\).
\[\left\{\begin{aligned} f[i][0] & amp;=f[i-2][0] + a[i] \ f[i][1 ] & amp;=\max (f[i-2][1], f[i-3][0]) + a[i] \ f[i][2] & amp;=\ \max (f[i-2][2], f[i-3][1], f[i-4][0]) + a[i] \end{aligned}\right. \ ]
const int N = 2e5 + 5;
int a[N];
ll f[N][3];
int main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int n; cin >> n;
for (int i = 1; i <= n; + + i) cin >> a[i];
for (int i = 1; i <= n; i + + )
for (int j = 0; j < 3; j + + )
f[i][j] = -1e18;
for (int i = 1; i <= 3; i + + )
f[i][i - 1] = a[i];
f[3][0] = a[1] + a[3];
for (int i = 4; i <= n; i + + ) {
f[i][0] = f[i - 2][0] + a[i];
f[i][1] = max(f[i - 2][1], f[i - 3][0]) + a[i];
f[i][2] = max(f[i - 2][2], f[i - 3][1]) + a[i];
if (i > 4) f[i][2] = max(f[i][2], f[i - 4][0] + a[i]);
}
ll ans;
if (n & 1) ans = max(f[n][2], max(f[n - 1][1], f[n - 2][0]));
else
ans = max(f[n][1], f[n - 1][0]);
cout << ans;
}