Hướng dẫn cho Bói Tình Bạn
Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.
Authors:
\(\color{red}{\text{Spoiler Alert}_{{}_{{}^{{}^{v2.0}}}}}\)
\(\color{red}{\text{Khuyến khích bạn đọc trước khi đọc phần lời giải xin hãy thử code ra thuật của mình dù nó có sai hay đúng}}\)
\(\color{red}{\text{Sau đó từ phần bài giải và thuật toán trước đó mà đối chiếu, rút nhận xét với thuật của mình và thu được bài học (không lãng phí thời gian đâu).}}\)
\(\color{orange}{\text{Hướng dẫn}}\)
- Mô phỏng:
Mỗi vòng lặp: duyệt qua các phần tử và tính giá trị mới, đồng thồi giảm số phần tử đi 1.
Thuật toán dừng khi số lượng còn 2
Độ phức tạp: \(O(n^2)\)
4 6 5 5 5 4 4 2
\ / \ / \ / \ / \ / \ / \ /
0 1 0 0 9 8 6
\ / \ / \ / \ / \ / \ /
1 1 0 9 7 4
\ / \ / \ / \ / \ / a b
2 1 9 6 1 \ /
\ / \ / \ / \ / c = (a + b) % 10
3 0 5 7
\ / \ / \ /
3 5 2
\ / \ /
8 7
-----
5
- Tính giá trị của một phần tử tại một thời điểm bằng truy hồi:
Gọi \(A_T\) là dãy \(A\) tại thời điểm \(T\) và còn \(|A_T| = |A| - T\) phần tử
Mỗi đệ quy: Giá trị của \(A_{T+1}[i]\) phụ thuộc vào \(A_T[i] + A_T[i + 1]\) nên từ đó ta có công thức truy hồi
Độ phức tạp: \(O(C_n^k)\) trâu, \(O(n \times k)\) quy hoạch động
5
/ \
8 7
/ \ / \
3 5 2
/ \ / \ / \ a' = (b' + c') mod 10
3 0 5 7 / \
/ \ / \ / \ / \ b' c'
2 1 9 6 1
/ \ / \ / \ / \ / \
1 1 0 9 7 4
/ \ / \ / \ / \ / \ / \
0 1 0 0 9 8 6
/ \ / \ / \ / \ / \ / \ / \
4 6 5 5 5 4 4 2
- Từ truy hồi nhìn ra công thức tổ hợp:
Thay vì truy hồi từng bước 1, từng thời gian một, ta có thể nhảy cóc bằng tổ hợp
Tính một lần \(A_T[i]\) thì tăng số lần giá trị của \(A_{T-1}[i + 0]\) lên \(1\) và \(A_{T-1}[i + 1]\) lên \(1\), và tính tổng lại
Tính một lần \(A_T[i]\) thì tăng số lần giá trị của \(A_{T-2}[i + 0]\) lên \(1\) và \(A_{T-2}[i + 1]\) lên \(2\) và \(A_{T-2}[i + 3]\) lên \(1\), và tính tổng lại
Tính một lần \(A_T[i]\) thì tăng số lần giá trị của \(A_{T-3}[i + 0]\) lên \(1\) và \(A_{T-3}[i + 1]\) lên \(3\) và \(A_{T-3}[i + 2]\) lên \(3\) và \(A_{T-3}[i + 3]\) lên \(1\), và tính tổng lại
\(\cdots\)
Từ \(A_T[i]\), thì số lần gọi phần tử \(A_{T-K}[i + P]\) trong tổng là \(C_K^P\)
\(\Rightarrow A_T[i] = \overset{P}{\underset{x = 0}{\Sigma}} (C_K^P \times A_{T-K}[i + P])\ mod\ 10\) (\(\forall T \geq K \geq 0\) và vị trí \(i\) phù hợp)
Gọi \(O(f(x))\) là độ phức tạp tính \(C_K^P\) thì độ phức tạp bài toán là \(O(f(x))\) vì mình chỉ cần gọi 2 lần
1 | 5 = (1x5) mod 10
/ \
1 1 | 5 = (1x7 + 1x8) mod 10
/ \ / \
1 2 1 | 5 = (1x3 + 2x5 + 1x2) mod 10
/ \ / \ / \ a'
1 3 3 1 / \ | 5 = (1x3 + 3x0 + 3x5 + 1x7) mod 10
/ \ / \ / \ / \ b' c'
1 4 6 4 1 | 5 = (1x2 + 4x1 + 6x9 + 4x6 + 1x1) mod 10
/ \ / \ / \ / \ / \ b' += a'
1 5 0 0 5 1 c' += a' | 5 = (1x1 + 5x1 + 0x0 + 0x9 + 5x7 + 1x4) mod 10
/ \ / \ / \ / \ / \ / \
1 6 5 0 5 6 1 | 5 = (1x0 + 6x1 + 5x0 + 0x0 + 5x9 + 6x8 + 1x6) mod 10
/ \ / \ / \ / \ / \ / \ / \
1 7 1 5 5 1 7 1 | 5 = (1x4 + 7x6 + 1x5 + 5x5 + 5x5 + 1x4 + 7x4 + 1x2) mod 10
\(\color{goldenrod}{\text{Tiếp cận}}\)
- Mô phỏng: Với mỗi bước tới khi nào số phần tử \(|A| = 2\)
Tạo mảng \(B\) gồm \(|A| - 1\) phần tử
Duyệt qua các phần tử và gán: \(B_i = (A_i + A_{(i+1)}) \mod 10\)
Gán lại mảng \(A = B\) (ban đầu cũng có thể sài trực tiếp mảng \(A\) nếu duyệt theo thứ tự)
- Truy hồi: Gọi \(f(T, i)\) là giá trị của \(A_{T}[i]\)
Ta có \(f(T, i) = f(T - 1, i - 1) + f(T - 1, i)\) khi \(T > 0\)
Ta có \(f(T, i) = a[i]\) khi \(T = 0\)
- Tổ hợp: Ta cần tối ưu độ phức tạp của \(O(f(x))\)
Tính \(C_n^k\) bằng công thức cộng \(C_n^k = C_{n-1}^k + C_{n-1}^{k-1}\) \(\Rightarrow\) Độ phức tạp \(O(C_n^k)\) khi trâu hoặc \(O(n \times k)\) với quy hoạch động
Ta sẽ tính \(C_n^k\) bằng công thức nhân \(C_n^k = \frac{n!}{k! (n-k)!}\)
Đầu tiên ta sẽ tính \(C_n^k\) khi modulo cho một số nguyên tố \(P\) khi \(P > n\). Ta cẩn thận không có phép chia modulo cho \(p!\)
Gọi \(fact_n = n! = 1 \times 2 \times \cdots \times n\)
Gọi \(tcaf_n = (n!)^{-1} = (n!)^{P-2}\)
Lưu ý: \(fact_0 = tcaf_0 = 1\)
Ta có \(C_n^k = \frac{n!}{k! (n-k)!} = n! \times k!^{-1} \times (n-k)!^{-1}\)
Hay \(C(n, k) = \frac{fact_n}{fact_k \times fact_{n-k}} = fact_n \times tcaf_k \times tcaf_{n-k}\)
Đầu tiên ta sẽ tính \(C_n^k\) khi modulo cho một số nguyên tố \(P\) khi \(P > 1\). Ta cẩn thận khi tính toán \(fact_p = 0\)
Gọi \(x = v \times P^k\) và \(f(x) = v\), \(g(x) = k\)
Gọi \(divp_n = \overset{n}{\underset{x = 1}{\Sigma}}(g(x))\)
Gọi \(fact_n = \overset{n}{\underset{x = 1}{\prod}}(f(x))\)
Gọi \(tcaf_n = fact_n ^ {P-2}\)
Ta có \(C_n^k = \frac{n!}{k! (n-k)!} = n! \times k!^{-1} \times (n-k)!^{-1}\)
Hay \(C(n, k) = \frac{fact_n}{fact_k \times fact_{n-k}} = fact_n \times tcaf_k \times tcaf_{n-k}\)
\(\cdots\)
- Editorial is dropped
Bài sử dụng tổ hợp nhưng dùng nghịch đảo modulo để tính giá trị tổ hợp trong \(O(1)\)
Bài sử dụng CRT để tính res mod 10 = (-5 * (res mod 2) + 6 * (res mod 5)) mod 10
\(\color{green}{\text{Code tham khảo }}\): CRT, Tổ hợp, Toán, Nghịch đảo Modulo
\(^{^{\color{purple}{\text{Độ phức tạp : }} O(n\ log\ n)\ \color{purple}{\text{thời gian}}\ ||\ O(n)\ \color{purple}{\text{bộ nhớ}}}}\)
#include <algorithm>
#include <iostream>
#include <vector>
#include <cstdio>
using namespace std;
#define all(x) (x).begin(), (x).end()
const int LIM = 1e6;
typedef long long ll;
void file(const string &FILE = "Test")
{
freopen((FILE + ".INP").c_str(), "r", stdin);
freopen((FILE + ".OUT").c_str(), "w", stdout);
}
int mulMOD(int a, int b, int MOD)
{
return ll(a) * b % MOD;
}
int powMOD(int x, int n, int MOD)
{
int res = 1;
for (; n > 0; n >>= 1)
{
if (n & 1) res = ll(res) * x % MOD;
x = ll(x) * x % MOD;
}
return res;
}
template<size_t MOD>
struct Combi
{
int divp[LIM + 1];
int fact[LIM + 1];
int tcaf[LIM + 1];
// int invs[LIM + 1];
Combi()
{
divp[0] = divp[1] = 0;
fact[0] = fact[1] = 1;
tcaf[0] = tcaf[1] = 1;
// invs[0] = invs[1] = 1;
for (int i = 2; i <= LIM; ++i)
{
int v = i, f = 0;
for (; v % MOD == 0; v /= MOD)
++f;
divp[i] = divp[i - 1] + f;
fact[i] = (fact[i - 1] * v) % MOD;
tcaf[i] = powMOD(fact[i], MOD - 2, MOD);
// invs[i] = ll(MOD - MOD / i) * invs[MOD % i] % MOD;
}
}
int query(int n, int k)
{
if (divp[n] > divp[k] + divp[n - k]) return 0;
return mulMOD(fact[n], mulMOD(tcaf[k], tcaf[n - k], MOD), MOD);
}
};
Combi<2> C2;
Combi<5> C5;
int nck10(int n, int k)
{
int res = ((-5LL * C2.query(n, k)) + (6LL * C5.query(n, k))) % 10;
if (res < 0) res += 10;
return res;
}
int nck(int n, int k)
{
if (k > n - k) k = n - k;
if (k < 0) return 0;
if (n == 0) return 1;
if (k == 0) return 1;
return nck(n - 1, k) + nck(n - 1, k - 1);
}
int solve(const vector<int> &a)
{
int res = 0;
int n = int(a.size()) - 1;
for (int i = 0; i <= n; ++i)
{
res += mulMOD(a[i], nck10(n, i), 10);
if (res >= 10) res -= 10;
}
return res;
}
int main()
{
//file();
int n, m;
cin >> n >> m;
n += m;
vector<int> a(n);
for (int i = 0; i < n; ++i)
{
string s;
cin >> s;
a[i] = s.size();
if (a[i] >= 10) a[i] = 0;
}
vector<int> left(all(a) - 1);
vector<int> right(1 + all(a));
cout << solve(left);
cout << solve(right);
return 0;
}
- Bài cũng có thể giải trong \(O(n)\) thời gian
Bình luận
Nể anh thiệt.Mới comment là anh làm liền.KINHHHHH!!!!
-
0
SPyofgame
9:33 p.m. 28 Tháng 2, 2021
1 bình luận nữaMặc dù nó đã bị delayed cả tháng (")>