Hướng dẫn giải của Hạnh phúc (HAPPY) (Đề HSG 12 Phú Thọ 2022-2023)
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Hướng dẫn giải
Đếm số xâu ~n~ chữ cái in hoa mà sau khi đọc từng chữ, tâm trạng (bắt đầu là hạnh phúc) kết thúc là hạnh phúc, lấy dư cho ~10^9 + 7~. Chữ S, D đặt tâm trạng hạnh phúc; H đặt không hạnh phúc; A, E, I, O, U đảo trạng thái; 18 chữ còn lại không đổi.
Sub 1: Vét cạn — ~O(26^n \cdot n)~, dùng khi ~n \le 4~
Duyệt mọi xâu, mô phỏng tâm trạng và đếm. Có ~26^n~ xâu nên chỉ dùng được khi ~n~ rất nhỏ: với ~n = 5~ đã có hơn 11 triệu xâu, chạy mất hơn 1 giây nên phải chuyển sang sub 2. Nếu chỉ nộp sub này: đúng 4/16 test.
Sub 2: Quy hoạch động theo độ dài — ~O(n)~, dùng khi ~n \le 10^7~
Chỉ quan tâm trạng thái cuối. Từ hạnh phúc: giữ nguyên với 20 chữ (S, D, 18 chữ trung tính), thành không hạnh phúc với 6 chữ (H và 5 nguyên âm). Từ không hạnh phúc: thành hạnh phúc với 7 chữ (S, D, 5 nguyên âm), giữ nguyên với 19 chữ. Lặp ~n~ lần. Kiểm tra ví dụ ~n = 2~: ~20 \cdot 20 + 6 \cdot 7 = 442~. Nếu chỉ nộp sub này: đúng 12/16 test.
Sub 3: Nhân ma trận lũy thừa — ~O(\log n)~
Phép chuyển trên là nhân với ma trận ~\begin{pmatrix} 20 & 6 \\ 7 & 19 \end{pmatrix}~, ta tính lũy thừa ~n~ bằng lũy thừa nhanh; kết quả là phần tử ở hàng 1, cột 1. Nếu chỉ nộp sub này: đúng 16/16 test.
Chương trình hoàn chỉnh
Hàm main đọc ~n~; ~n \le 5~ gọi sub1, ~n \le 10^7~ gọi sub2, còn lại gọi sub3. Khi đi thi nên viết như vậy: sub sau có sai hoặc chưa kịp làm thì vẫn ăn điểm sub trước.
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007;
long long n;
// Sub 1: vét cạn mọi xâu n chữ cái (26^n xâu), dùng khi n <= 4 (n = 5 đã có hơn 11 triệu xâu, quá chậm)
void sub1() {
int cnt = 0;
long long total = 1;
for (int i = 0; i < n; i++) total *= 26;
for (long long code = 0; code < total; code++) {
long long c = code;
bool happy = true;
for (int i = 0; i < n; i++) {
char ch = 'A' + c % 26; c /= 26;
if (ch == 'S' || ch == 'D') happy = true;
else if (ch == 'H') happy = false;
else if (strchr("AEIOU", ch)) happy = !happy;
}
if (happy) cnt++;
}
printf("%d\n", cnt);
}
// Sub 2: quy hoạch động theo độ dài, O(n), dùng khi n <= 10^7
// h = số xâu kết thúc hạnh phúc, u = số xâu kết thúc không hạnh phúc
// hạnh phúc -> hạnh phúc: 20 chữ (S, D và 18 chữ trung tính); hạnh phúc -> không: 6 chữ (H và 5 nguyên âm)
// không -> hạnh phúc: 7 chữ (S, D và 5 nguyên âm); không -> không: 19 chữ (H và 18 chữ trung tính)
void sub2() {
long long h = 1, u = 0;
for (long long i = 0; i < n; i++) {
long long nh = (h * 20 + u * 7) % MOD;
long long nu = (h * 6 + u * 19) % MOD;
h = nh; u = nu;
}
printf("%lld\n", h);
}
typedef array<array<long long, 2>, 2> Mat;
Mat mul(const Mat& a, const Mat& b) {
Mat c = {};
for (int i = 0; i < 2; i++)
for (int j = 0; j < 2; j++)
for (int k = 0; k < 2; k++) c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % MOD;
return c;
}
// Sub 3: nhân ma trận 2x2 lũy thừa nhanh, O(log n)
void sub3() {
Mat M = {{{20, 6}, {7, 19}}}, R = {{{1, 0}, {0, 1}}};
long long e = n;
while (e) {
if (e & 1) R = mul(R, M);
M = mul(M, M);
e >>= 1;
}
printf("%lld\n", R[0][0]); // bắt đầu ở trạng thái hạnh phúc, kết thúc hạnh phúc
}
int main() {
freopen("HAPPY.INP", "r", stdin);
freopen("HAPPY.OUT", "w", stdout);
scanf("%lld", &n);
if (n <= 4) sub1();
else if (n <= 10000000) sub2();
else sub3();
return 0;
}
Bình luận