Hướng dẫn giải của [KHTN - Thi thử TS10 #2 - 2025] Bài 2: ONES
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
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.
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.
Tóm tắt đề bài
Cho số gồm ~n~ chữ số ~1~. Ví dụ, với ~n = 4~ ta có số ~1111~.
Hãy tính ~n~ ~\%~ ~998244353~.
Subtask 1: ~n \le 18~
Ta có thể tính hẳn giá trị ~n~ ra, sau đó tìm ra kết quả.
Ta có thể xây dựng từng chữ số như sau:
cpp=
int res = 0;
for (int i = 1; i <= n; i++){
res *= 10; // Lúc này, số đã có thêm một chữ số 0.
res += 1; // Ta thay chữ số 0 thành chữ số 1.
}
Cuối cùng, ta in ra kết quả.
Độ phức tạp: ~O~ (~n~).
Subtask 2: ~n \le 10^5~
Nhìn vào công thức truy hồi trên, thay vì nhân hết rồi mới mod, ta có thể mod ngay khi nhân, do tính chất của phép cộng và nhân đều có thể modulo được.
Độ phức tạp: ~O~ (~n~).
Bình luận