💻
Elearning
CodePath
Problems
Contests
Roadmap
🔐 Login
Xử lý Xâu Nhị Phân và Truy Vấn
HASH001
### 📌 Thông tin chung | Mục | Chi tiết | | :--- | :--- | | **Tên File Input** | `BINQ.INP` | | **Tên File Output** | `BINQ.OUT` | | **MODULO** | $1007050321$ | --- ### 📝 Bài toán Cho một xâu nhị phân $S$ ban đầu. Ta cần xử lý 2 loại truy vấn có dạng như sau: 1. **Xóa (Type 1):** Xóa ký tự ở vị trí $P$. Vị trí các ký tự trong xâu được đánh dấu lại. 2. **Truy vấn (Type 0):** Từ một đoạn con $[L, R]$ của xâu hiện tại, ta cần in ra số ở hệ thập phân được biểu diễn từ đoạn con trên. Vì kết quả có thể rất to nên ta chỉ cần in kết quả lấy dư cho $1007050321$. Công thức tính giá trị thập phân $V$ của đoạn con nhị phân $S[L..R]$: $V = \sum_{i=L}^{R} S[i] \times 2^{(R - i)} \pmod{1007050321}$ --- ### 📥 Định dạng Đầu vào * Dòng đầu tiên là một xâu nhị phân $S$. * Dòng tiếp theo gồm số nguyên $Q$ là số lượng truy vấn. * $Q$ dòng tiếp theo, mỗi dòng là một trong 2 loại truy vấn: * **Type 1:** Gồm `1 P` (xóa ký tự ở vị trí $P$). * **Type 0:** Gồm `0 L R` (truy vấn đoạn $[L, R]$). Giới hạn: * $|S| \le 10^5$. * $Q \le 10^5$. * Các số $P, L, R$ trong mỗi test đảm bảo không vượt quá độ dài sâu hiện tại. --- ### 📤 Định dạng Đầu ra Với mỗi thao tác loại 0, in ra đáp án cần tìm ($\pmod{1007050321}$). --- ### ✨ Ví dụ | Input | Output | | :---: | :---: | | `00111` <br> `3` <br> `0 1 5` <br> `1 3` <br> `0 3 4` | `7` <br> `3` | Giải thích ví dụ: 1. **Ban đầu:** $S = 00111$. 2. **Truy vấn `0 1 5`:** $S[1..5] = 00111$. * Giá trị thập phân: $0\cdot 2^4 + 0\cdot 2^3 + 1\cdot 2^2 + 1\cdot 2^1 + 1\cdot 2^0 = 4 + 2 + 1 = 7$. Output: **7**. 3. **Truy vấn `1 3`:** Xóa ký tự tại vị trí 3 (là '1'). * $S$ mới: $00\mathbf{1}11 \to 0011$. Độ dài mới là 4. 4. **Truy vấn `0 3 4`:** $S[3..4] = 11$. * Giá trị thập phân: $1\cdot 2^1 + 1\cdot 2^0 = 2 + 1 = 3$. Output: **3**. --- ### 🏷 Subtasks | Subtask | Ràng buộc | Tỷ lệ điểm | | :--- | :--- | :--- | | $1$ | $abs(S), Q \le 1000$ | $30\%$ | | $2$ | $abs(S), Q \le 5 \times 10^4$ | $30\%$ | | $3$ | $abs(S), Q \le 10^5$ | $40\%$ | ---
✅ Đã AC: 0 / 0 submissions
⬅ Contest
🚀 Nộp bài
💡 Gợi ý AI
📌 Bài kế
📋 Copy đề
⚙️
⬅ Contest
🚀 Nộp bài
💡 Gợi ý
📌 Bài kế
📋 Copy
📖 Hướng dẫn học tập
Học trò tri ân
☕ Một ly cà phê sẻ chia
Bạn bè ủng hộ
🍜 Một bát phở ấm lòng
💳 Quét mã ủng hộ tuỳ tâm nhé!
💬 Liên hệ Zalo!
Đóng