PVHOI3 - Bài 6: Chữ số không

Xem PDF
Tác giả:
Flower_On_Stone , skyvn97
Dạng bài
Điểm: 2700 (p) Thời gian: 8.0s Bộ nhớ: 1G Input: KHONG.inp Output: KHONG.out

Cho dãy số nguyên dương \(a_{1}, a_{2}, \ldots, a_{n}\). Bạn cần thực hiện \(q\) thao tác trên dãy số này, mỗi thao tác thuộc một trong ba dạng dưới đây:

  • A l r x y: Xét các số \(a_{l}, a_{l + 1}, a_{l+2}, \ldots, a_{r}\); bạn cần nhân các số này với lần lượt các giá trị \(x, x + y, x + 2 \cdot y, \ldots, x + (r-l) \cdot y\). Nói cách khác, với mọi chỉ số \(i\) sao cho \(l \leq i \leq r\), ta thay phần thử \(a_{i}\) bởi \(a_{i} \cdot (x + (i-l) \cdot y)\).
  • G l r x y: Xét các số \(a_{l}, a_{l + 1}, a_{l+2}, \ldots, a_{r}\); bạn cần nhân các số này với lần lượt các giá trị \(x, x \cdot y, x \cdot y^{2}, \ldots, x \cdot y^{r - l}\). Nói cách khác, với mọi chỉ số \(i\) sao cho \(l \leq i \leq r\), ta thay phần thử \(a_{i}\) bởi \(a_{i} \cdot x \cdot y^{i - l}\).
  • C l r: Xét số nguyên dương \(P = a_{l} \cdot a_{l + 1} \cdot a_{l + 2} \cdot \ldots \cdot a_{r}\); bạn cần tìm số chữ số không ở ngoài cùng bên phải khi viết số \(P\) trong hệ thập phân. Nói cách khác, bạn cần tìm số nguyên không âm \(k\) lớn nhất sao cho \(P\) chia hết cho \(10^{k}\).

Bạn hãy viết chương trình thực hiện các yêu cầu trên.

Input

  • Dòng đầu tiên chứa số nguyên \(\theta\) \((1 \leq \theta \leq 6)\) là số thứ tự của subtask chứa test này.
  • Dòng thứ hai chứa hai số nguyên \(n\) và \(q\) \((1 \leq n, q \leq 200311)\)
  • Dòng thứ ba chứa \(n\) số nguyên \(a_{1}, a_{2}, \ldots, a_{n}\) \((1 \leq a_i \leq 10^{6})\) mô tả dãy số ban đầu.
  • Trong \(q\) dòng cuối cùng, mỗi dòng thể hiện một thao tác thuộc một trong ba dạng sau:
    • A l r x y với \(1 \leq l \leq r \leq n, 1 \leq x \leq 10^{6}\) và \(0 \leq y \leq 10^{6}\)
    • G l r x y với \(1 \leq l \leq r \leq n\) và \(1 \leq x, y \leq 10^{6}\)
    • C l r với \(1 \leq l \leq r \leq n\)

Output

  • Với mỗi thao tác thuộc dạng \(C\), in ra kết quả trên một dòng.

Scoring

  • Subtask \(1\) (\(10\) điểm): n,q≤1000
  • Subtask \(2\) (\(10\) điểm): Mọi thao tác loại A có \(y = 0\) và mọi thao tác loại G có \(y = 1\).
  • Subtask \(3\) (\(10\) điểm): Mọi thao tác loại A có \(y = 0\).
  • Subtask \(4\) (\(10\) điểm): Mọi thao tác loại A có \(y = 1\).
  • Subtask \(5\) (\(10\) điểm): Mọi thao tác loại C có \(l = 1\) và \(r = n\).
  • Subtask \(6\) (\(10\) điểm): Không có ràng buộc gì thêm.

Example

Test 1

Input 
1
7 5
2 2 7 1 9 9 7
A 2 4 6 3
G 4 6 5 2
C 1 5
C 2 6
C 3 7
Output 
2 3 3
Note

Dãy số ban đầu là \((2, 2, 7, 1, 9, 9, 7)\).

  • Trong thao tác đầu tiên, các số \((a_{2}, a_{3}, a_{4})\) lần lượt được nhân với \(6, 9\) và \(12\). Sau thao tác này, dãy số trở thành \((2, 12, 63, 12, 9, 9, 7)\).
  • Trong thao tác thứ hai, các số \((a_{4}, a_{5}, a_{6})\) lần lượt được nhân với \(5, 10\) và \(20\). Sau thao tác này, dãy số trở thành \((2, 12, 63, 60, 90, 180, 7)\).
  • Trong thao tác thứ ba, ta có \(a_{1} \cdot a_{2} \cdot a_{3} \cdot a_{4} \cdot a_{5} = 8164800\) có tận cùng \(2\) chữ số \(0\).
  • Trong thao tác thứ tư, ta có \(a_{2} \cdot a_{3} \cdot a_{4} \cdot a_{5} \cdot a_{6} = 734832000\) có tận cùng \(3\) chữ số \(0\).
  • Trong thao tác thứ năm, ta có \(a_{3} \cdot a_{4} \cdot a_{5} \cdot a_{6} \cdot a_{7} = 428652000\) có tận cùng \(3\) chữ số \(0\).

Bình luận