## Solution CHV training [1]
https://oj.vnoi.info/contest/chvgl_chv
# 1. Sum T.
___
> ###### Tags: Two pointers, Binary Search.
> https://oj.vnoi.info/problem/chvgl_sumt
___
### **Nhận xét** :
+ Ta chỉ xét trên một đoạn liên tục trong dãy, cũng như các phần tử trong mảng là dương.
+ Ta cho thể nhận thấy được rằng nếu có đoạn con độ dài $x$ thỏa mãn điều kiện thì các đoạn con có độ dài $1, 2..\;, x - 1$ cũng thỏa mãn điều kiện.
=> Từ đó ta có thể áp dụng **Two pointers, Binary Search**.
### **Giải theo Binary Search :**
* Như nhận xét trên ta sẽ tìm kiếm kết quả trên đoạn $[l, \; r]$, nếu giá trị $mid$ đang kiểm tra thỏa mãn ta sẽ kiểm tra trên đoạn $[mid + 1, \; r]$, ngược lại $[l, \; mid - 1]$. Giá trị $x$ chỉ thỏa mãn khi tồn tại ít nhất một đoạn liên tiếp độ dài $k$ có tổng nhỏ hơn $t$.
**Code**
> **Time : $O(n * log\;n$)**
> **Tags : Binary Search, Prefix sum**
```Cpp=
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, l, r) for (int i = (l); i <= (r); ++i)
const int INF = 1e9;
const int N = 1e5 + 5;
int n, s, pre[N];
bool check(int len) {
if (len > n) return 0;
FOR(i, 1, n - len + 1)
if (pre[i + len - 1] - pre[i - 1] <= s) return 1;
return 0;
}
void test_case() {
cin >> n >> s;
FOR(i, 1, n) cin >> pre[i], pre[i] += pre[i-1];
if (pre[n] <= s) {
cout << n;
return;
}
int l = 1, r = N;
while (l <= r) {
int mid = (l + r) >> 1;
if (check(mid)) l = mid + 1;
else r = mid - 1;
}
cout << l - 1;
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int TC = 1;
while (TC--) test_case();
return 0;
}
```
### **Giải theo Two pointers:**
* Có thể tham khảo qua : [https://vnoi.info/wiki/algo/basic/two-pointers.md](https://vnoi.info/wiki/algo/basic/two-pointers.md)
**Code :**
> **Time : $O(n$)**
> **Tags : Two pointers**
```cpp=
#include<bits/stdc++.h>
using namespace std;
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define MASK(i) (1ll << (i))
#define BIT(x, i) (((x) >> (i)) & 1ll)
#define builtin_popcount __builtin_popcountll
#define Times cerr <<"\nTime: "<<clock()/(double)1000<<" sec"
// cout << setprecision(0) << fixed << ans;
const int N = (int)1e5 + 5;
const int Sz = (int)1e6 + 5;
const int INF = (int)1e9;
const int MOD = (int)1e9 + 7;
/***------------------------- END ---------------------------***/
int n, k, a[N];
#define TASK ""
int main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#ifndef ONLINE_JUDGE
// freopen(TASK".inp", "r", stdin);
// freopen(TASK".out", "w", stdout);
#endif
cin >> n >> k;
for (int i = 1; i <= n; i++) cin >> a[i];
int res = 0, l = 1, sum = 0;
for (int r = 1; r <= n; r++) {
sum += a[r];
while (sum > k) sum -= a[l++];
res = max(res, r - l + 1);
}
cout << res;
return 0;
}
// DP_196
```
# 2. K - Sum.
---
[https://oj.vnoi.info/problem/chvgl_kth](https://oj.vnoi.info/problem/chvgl_kth)
##### Tags : Sort, CTDL C++.
---
### Subtask 1 ($n <= 10 ^ 5$) :
* Ta có thể sort mảng lại, hoặc dùng các CTDL để chọn ra $k$ phần tử đầu tiên trong mảng với độ phức tạp là **$O(n * log \; n)$**.
### Subtask 2 ($n <= 10 ^ 6$) :
* Khi bài toán chỉ còn $0.15s$ thì cách giải của **subtask 1** không còn phù hợp nữa. Thì với trường hợp này đối với $C++$ thì ta sẽ dùng lệnh **nth_element**. Cách dùng như sau :
* **Cú pháp :** (tên mảng + chỉ số đầu, tên mảng + giá trị $k$, tên mảng + chỉ số cuối).
* **Ý nghĩa :** Sau khi thực hiện lệnh này $k$ phần tử bé nhất của mảng sẽ được đẩy lên $k$ vị trí đầu tiên của mảng.
* **Lưu ý** : Sau khi lệnh được thực thi thì $k$ phần tử đầu tiên của mảng là $k$ giá trị bé nhất, nhưng không có nghĩa $k$ phần tử này được sắp xếp tăng dần.
* **Độ phức tạp** : $O(n)$.
**Code :**
```cpp=
#include<bits/stdc++.h>
using namespace std;
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define MASK(i) (1ll << (i))
#define BIT(x, i) (((x) >> (i)) & 1ll)
#define builtin_popcount __builtin_popcountll
#define Times cerr <<"\nTime: "<<clock()/(double)1000<<" sec"
// cout << setprecision(0) << fixed << ans;
const int N = (int)1e5 + 5;
const int Sz = (int)1e6 + 5;
const int INF = (int)1e9;
const int MOD = (int)1e9 + 7;
/***------------------------- END ---------------------------***/
int n, k, a[Sz];
#define TASK ""
int main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#ifndef ONLINE_JUDGE
// freopen(TASK".inp", "r", stdin);
// freopen(TASK".out", "w", stdout);
#endif
cin >> n >> k;
for (int i = 1; i <= n; i++) cin >> a[i];
nth_element(a + 1, a + k, a + n + 1);
int64_t res = 0;
for (int i = 1; i <= k; i++) res += a[i];
cout << res;
return 0;
}
// DP_196
```
> 10 người đọc đề hết 11 người tưởng mình sẽ AC sau 30 s :))))))
# 3. Hihi
___
[https://oj.vnoi.info/problem/chvgl_hihi](https://oj.vnoi.info/problem/chvgl_hihi)
###### Tags: Sort, Two pointers.
**Code :**
> **Time : $O(n * log \; n$)**
```Cpp==
#pragma GCC optimize("unroll-loops,02,no-stack-protector")
#include<bits/stdc++.h>
using namespace std;
#define TASK ""
#define p first
#define t second
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define MASK(i) (1ll << (i))
#define BIT(x, i) (((x) >> (i)) & 1ll)
#define builtin_popcount __builtin_popcountll
typedef pair<int, int> ii;
const int N = (int)1e5 + 5;
const int Sz = (int)1e6 + 5;
const int INF = (int)1e9;
const int MOD = (int)1e9 + 7;
void setIO() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
// freopen(TASK".inp","r",stdin);
// freopen(TASK".out","w",stdout);
}
/***------------------------- END ---------------------------***/
int n, m, res = INF;
ii a[N];
unordered_map<int, int> cnt;
int main() {
setIO();
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i].p >> a[i].t;
cnt[a[i].t]++;
}
sort(a + 1, a + n + 1);
m = sz(cnt);
cnt.clear();
int l = 1;
for (int r = 1; r <= n; r++) {
cnt[a[r].t]++;
while (l <= r && cnt[a[l].t] > 1) --cnt[a[l++].t];
if (sz(cnt) == m) res = min(res, a[r].p - a[l].p);
}
cout << res;
return 0;
}
// DP_196
```
# 4. 196.
___
##### Tags : Nhân ma trận (Matrix multiplication).
[https://oj.vnoi.info/problem/chvgl_196](https://oj.vnoi.info/problem/chvgl_196)
**Tham khảo** : [https://vnoi.info/wiki/algo/trick/matrix-multiplication.md](https://vnoi.info/wiki/algo/trick/matrix-multiplication.md)
___
### Với $n <= 10 ^ 6:$
+ Các bạn có thể chạy tuyến tính để tạo ra mảng $f[i]$.
### Với $n <= 10 ^ {18}:$
+ Hiển nhiên cách làm thông thường là tính lần lượt các $f[i]$. Tuy nhiên, cách làm này hoàn toàn không hiệu quả với $n$ lên đến $n <= 10 ^ {18}$, và ta cần một cách tiếp cận khác.
+ Ta xét các lớp số :
* Lớp 1 : $f[1], \: f[2], \: f[3]$
* Lớp 2 : $f[2], \: f[3], \: f[4]$
* ...
* Lớp i : $f[i], \: f[i - 1], \: f[i - 3]$
+ Ta hình dung mỗi lớp là một ma trận $(3 × 1)$. Tiếp đó, ta sẽ biến đổi từ lớp $i - 1$ đến lớp $i$. Sau mỗi lần biến đổi như vậy, ta tính thêm được một giá trị $f[i]$. Để thực hiện phép biến đổi này, chú ý là các số ở lớp sau chỉ phụ thuộc vào lớp ngay trước nó theo các phép cộng, ta tìm được cách biến đổi bằng nhân ma trận:
+ $$
A \: ×
\begin{bmatrix}
f[i - 1] \\
f[i - 2] \\
f[i - 3]
\end{bmatrix}
=
\begin{bmatrix}
f[i] \\
f[i - 1] \\
f[i - 2]
\end{bmatrix}
$$
* Ma trận $A$ (Ma trận cơ sở - Các bạn tham khảo qua **VNOI**) ở đây sẽ là :
* $$
A =
\begin{bmatrix}
1 & 9 & 6 \\[0.3em]
1 & 0 & 0 \\[0.3em]
0 & 1 & \ 0
\end{bmatrix}
$$
### Code :
___
> Times : $O(3 ^ 3 * q * log \: n)$
___
```Cpp=
#pragma GCC optimize("unroll-loops,02,no-stack-protector")
#include<bits/stdc++.h>
using namespace std;
#define TASK ""
#define int int64_t
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define MASK(i) (1ll << (i))
#define BIT(x, i) (((x) >> (i)) & 1ll)
#define builtin_popcount __builtin_popcountll
const int N = (int)1e5 + 5;
const int Sz = (int)1e6 + 5;
const int INF = (int)1e9;
const int MOD = (int)1e9 + 7;
void setIO() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
// freopen(TASK".inp","r",stdin);
// freopen(TASK".out","w",stdout);
}
/***------------------------- END ---------------------------***/
int ntest, n;
struct Matrix {
int a[4][4] = {{0, 0}, {0, 0}, {0, 0}};
Matrix operator * (const Matrix& other) const {
Matrix product;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
for (int k = 0; k < 3; k++)
product.a[i][k] = (product.a[i][k] +
a[i][j] * other.a[j][k] % MOD) % MOD;
}
}
return product;
}
};
Matrix pw(Matrix a, int k) {
Matrix res;
for (int i = 0; i < 3; i++) res.a[i][i] = 1;
while (k) {
if (k & 1) res = res * a;
k >>= 1;
a = a * a;
}
return res;
}
int32_t main() {
setIO();
cin >> ntest;
Matrix s;
s.a[1][0] = s.a[2][1] = 1;
s.a[0][2] = 6;
s.a[1][2] = 9;
s.a[2][2] = 1;
for (int k = 1; k <= ntest; k++) {
cin >> n;
if (n <= 1) cout << "1\n";
else if (n <= 2) cout << "9\n";
else if (n <= 3) cout << "6\n";
else {
Matrix tmp = pw(s, n - 3);
int res = ((tmp.a[0][2] + 9 * tmp.a[1][2] % MOD) % MOD + 6 * tmp.a[2][2] % MOD) % MOD;
cout << res << '\n';
}
}
return 0;
}
// DP_196
```
# 5. Tổng các ước.
___
[https://oj.vnoi.info/problem/chvgl_sdiv](https://oj.vnoi.info/problem/chvgl_sdiv)
___
## Các kiến thức cần có :
* Sàng nguyên tố, phân tích thừa số nguyên tố với thời gian thực hiện hợp lí.
* Sàng nguyên tố $O(n * log \: n)$, với mảng $prime[i]$ là số nguyên tố bé nhất mà $i$ chia hết cho số đó:
```cpp=
for (int i = 2; i * i < Sz; i++)
if (!prime[i])
for (int j = i * i; j < Sz; j += i)
if (!prime[j]) prime[j] = i;
for (int i = 2; i < Sz; i++) if (!prime[i]) prime[i] = i;
```
* Phân tích thừa số nguyên tố trong $O(log \: n)$ :
```cpp=
void factlog(int n) {
while (n != 1)
mark[prime[n]]++, n /= prime[n];
}
```
* Các kiến thức về toán học, phép đồng dư.
* Công thức tính tổng ước.
* Khi số $MOD$ là số nguyên tố thì ta sẽ có : $(a \: / \: b)$ % $MOD = a \: * \: pow(b, \: MOD - 2)$ % $MOD$.
## Code :
___
> Tags : Math
> Times : $O(n * log \: n)$
___
```Cpp=
#include<bits/stdc++.h>
using namespace std;
#define int int64_t
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define MASK(i) (1ll << (i))
#define BIT(x, i) (((x) >> (i)) & 1ll)
#define builtin_popcount __builtin_popcountll
#define Times cerr <<"\nTime: "<<clock()/(double)1000<<" sec"
// cout << setprecision(0) << fixed << ans;
const int N = (int)1e5 + 5;
const int Sz = (int)1e6 + 5;
const int INF = (int)1e9;
const int MOD = (int)1e9 + 7;
/***------------------------- END ---------------------------***/
int n, k, prime[Sz];
unordered_map<int, int> mark;
void factlog(int n) {
while (n != 1)
mark[prime[n]]++, n /= prime[n];
}
int pw(int x, int n) {
int res = 1;
while (n > 0) {
if (n & 1) res = res * x % MOD;
n >>= 1;
x = x * x % MOD;
}
return res;
}
#define TASK ""
int32_t main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
// #ifndef ONLINE_JUDGE
// freopen(TASK".inp", "r", stdin);
// freopen(TASK".out", "w", stdout);
// #endif
for (int i = 2; i * i < Sz; i++)
if (!prime[i])
for (int j = i * i; j < Sz; j += i)
if (!prime[j]) prime[j] = i;
for (int i = 2; i < Sz; i++) if (!prime[i]) prime[i] = i;
cin >> n;
for (int i = 1; i <= n; i++) {
int x;
cin >> x;
factlog(x);
}
cin >> k;
for (auto it : mark) mark[it.first] = it.second * k;
int res = 1;
for (auto it : mark) {
int a = (pw(it.first, it.second + 1) - 1 + MOD) % MOD;
int b = pw(it.first - 1, MOD - 2);
res = ((res * a) % MOD * b % MOD) % MOD;
}
cout << res;
return 0;
}
// DP_196
```
> Ai có thắc mắc hãy liên hệ qua : [https://www.facebook.com/profile.php?id=100040553432971](https://www.facebook.com/profile.php?id=100040553432971). Đoạn sau lười quá nên không viết nữa mong mọi người thông cảm =((
{"metaMigratedAt":"2023-06-17T04:16:58.886Z","metaMigratedFrom":"YAML","title":"CHV training [1]","breaks":true,"contributors":"[{\"id\":\"3d74aaa0-36da-4c3b-ae6c-454a8b6c8fd7\",\"add\":12521,\"del\":477}]"}