Bình luận

• 
  

  1

  

  PDNAM  đã bình luận lúc 21, Tháng 7, 2024, 14:19 ← sửa 2 →

  my sol:

  với bài toán con 1 , ta xây dựng một mảng sum , với sum[i] có ý nghĩa là số mà xâu con từ 1 -> i tạo thành modulo cho 33.(hiển nhiên 1 <= i <= n); nhận thấy đoạn con u -> v chia hết cho 33 khi và chỉ khi sum[v] = ( sum[u - 1] * 10 ^ (v - u + 1) ) modulo 33 nhận thấy tính chất dố nên ta cho thể sử dụng mảng d để đếm phân phối , với d[i] (0 <= i <= 32) nghĩa là số lượng (sum[j] * 10 ^ (n - j)) modulo 33 mà = i (1 <= j <= n) cuối cùng duyệt qua từng d[i] và ans += d[i] * (d[i] - 1) / 2; dpt O(n);

  với bài toán con 2 , ta xây dựng thêm một mảng kiểu pair dd , với dd[i].first là số j đầu tiên mà (sum[j] * 10 ^ (n - j)) modulo 33 mà = i , còn dd[i].second là số j cuối thoả mãn chỉ việc so sánh từng số dc tạo thành từ xâu con đánh chỉ số từ dd[i].first + 1 đến dd[i].second thôi tối đa chỉ xét tới 33 số nên dpt là O(33 * n);