VOI 21 Bài 3 - Phép toán OR

View as PDF

Submit solution


Points: 1.50 (partial)
Time limit: 1.0s
Memory limit: 1G
Input: stdin
Output: stdout

Suggester:
Problem source:
Kỳ thi Học sinh giỏi Quốc gia 2021 - Ngày 1
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

In case the statement didn't load correctly, you can download the statement here: Statement

Nội dung chính trong tiết học Tin học trên lớp của Nam ngày hôm nay là về phép toán OR. Phép toán OR (có kí hiệu là |) được định nghĩa như sau: Kết quả của phép toán OR giữa 2 số nguyên không âm ~x~ và ~y~ là một số nguyên không âm ~z~ trong đó bit thứ ~i~ trong biểu diễn nhị phân của ~z~ sẽ là ~0~ khi và chỉ khi bit thứ ~i~ trong biểu diễn nhị phân của ~x~ và ~y~ đồng thời bằng ~0~, ngược lại bit thứ ~i~ trong biểu diễn nhị phân của ~z~ là ~1~.

Ví dụ, ~x = 12~ có biểu diễn nhị phân là 1100, ~y = 5~ có biểu diễn nhị phân là 0101, khi đó ~x | y~ có biểu diễn nhị phân là 1101, tức giá trị ~13~ trong hệ cơ số thập phân.

Phép toán OR có tính chất giao hoán và kết hợp: ~x | y = y | x~ và ~x | (y | z) = (x | y) | z~.

Để ôn tập nội dung đã học, thầy giáo ra cho cả lớp bài tập về nhà như sau: Cho ~n~ số nguyên không âm ~a_1, a_2, \dotsc, a_n~ và ba số nguyên ~k, L, R~. Hãy đếm xem có bao nhiêu bộ ~k~ chỉ số ~(i_1, i_2, \dotsc, i_k)~ thỏa mãn đồng thời hai điều kiện:

  • ~1 \le i_1 < i_2 < \dotsc < i_k \le n~.
  • Đặt ~v = a_{i_1} | a_{i_2} | \dotsc | a_{i_k}~ thì ~L \le v \le R~ và ~v~ chia hết cho 3.

Gọi ~S~ là đáp số đúng cho bài tập thầy giáo ra, vì ~S~ có thể có giá trị rất lớn và để học sinh tập trung vào vấn đề chính của bài toán nên thầy giáo chỉ yêu cầu học sinh đưa ra được phần dư của ~S~ khi chia cho ~10^9 + 7~.

Yêu cầu: Hãy giúp Nam xác định phần dư của ~S~ khi chia cho ~10^9 + 7~.

Dữ liệu

Vào từ đầu vào chuẩn (không phải file OR.INP):

  • Dòng đầu tiên chứa bốn số nguyên ~n, k, L, R (1 \le k \le n \le 10^6; 0 \le L \le R \le 10^6)~;
  • Dòng tiếp theo chứa ~n~ số nguyên không âm ~a_1, a_2, \cdots, a_n~ ~(a_i \le 10^6)~.

Các số trên cùng một dòng cách nhau bởi dấu cách.

Kết quả

Ghi ra đầu ra chuẩn (không phải file OR.OUT) một số nguyên duy nhât là phần dư của ~S~ khi chia cho ~10^9+7~.

Ràng buộc

  • Có ~20\%~ số test ứng với ~20\%~ số điểm của bài thỏa mãn ~n \le 20~ và ~a_i \le 200 (1 \le i \le n)~;
  • Có ~20\%~ số test khác ứng với ~20\%~ số điểm của bài thỏa mãn ~n \le 200~ và ~a_i \le 200 (1 \le i \le n)~;
  • Có ~20\%~ số test khác ứng với ~20\%~ số điểm của bài thỏa mãn ~L = R~ và ~a_i(1 \le i \le n)~ là lũy thừa của 2;
  • Có ~20\%~ số test khác ứng với ~20\%~ số điểm của bài thỏa mãn ~L = R~ ;
  • Có ~20\%~ số test còn lại ứng với ~20\%~ số điểm của bài không có ràng buộc gì thêm.

Ví dụ

Input
5 2 1 7
1 2 5 6 4
Output
4
Giải thích

Có tất cả 4 cách chọn 2 số trong 5 số thỏa mãn yêu cầu:

  1. ~a_1 | a_2 = 1 | 2 = 3~
  2. ~a_2 | a_4 = 2 | 6 = 6~
  3. ~a_2 | a_5 = 2 | 4 = 6~
  4. ~a_4 | a_5 = 6 | 4 = 6~

Comments

Please read the guidelines before commenting.



  • 11
    darkkcyan  commented on Dec. 30, 2021, 11:45 a.m.

    Sau khi update server, bộ test mới nhất có vẻ đã bị tráo lại thành bộ test cũ. Bộ test mới nhất đã được đăng lên lại và các submission trở lại gần đây sẽ được rejudge. Xin lỗi các bạn về sự cố này :(.


  • 11
    darkkcyan  commented on Dec. 13, 2021, 2:50 p.m.

    Lại một lần nữa xin lỗi các bạn vì mình sinh test có sai dữ kiện đề bài. Trong subtask 3 có dữ kiện các số đều phải là lũy thừa của 2, nhưng trong bộ test mình sinh ra có cả số ~0~ :(.

    Mình đã viết thêm cả validator và sửa lại lần nữa thuật toán sinh test. Mình cũng có thêm 1 số lựa chọn sinh test nữa để đảm bảo bộ test được mạnh hơn.

    Mình đã rejudge lại toàn bộ submission AC, RTE và TLE. Các submission còn lại chiến khoảng 1/2 lượng submissions nên mình xin phép không rejudge chúng. Sau khi rejudge thì có 7 submissions mất verdict AC. Các submission RTE trước đó có vẻ như không có thay đổi gì cả. Còn submission TLE có giảm nhưng chủ yêu lại sang WA hoặc RTE, ngoại trừ 2 submissions đã AC sau lần rejudge lại này.


    • 3
      DP_196  commented on Nov. 23, 2022, 8:50 a.m.

      Nhưng mà hình như subtask 4 lại thiếu số 0 ạ . Em duyệt các dãy bit con của L, em quên xét bit 0. Thế mà vẫn qua anh ạ!


    • 1
      kazamahoang  commented on Dec. 14, 2021, 11:39 a.m.

      bảo sao em trâu sai =))))


      • 7
        darkkcyan  commented on Dec. 14, 2021, 12:41 p.m.

        Nếu bạn có vấn đề gì về bộ test thì bạn có thể report giúp chúng mình nha!


  • 8
    darkkcyan  commented on July 25, 2021, 1:43 p.m.

    Bộ test mới được cập nhật lại do sai làm nhỏ trong việc sinh test. Đề bài nói rằng giới hạn của ~L, R~ là từ ~0~ đến ~10^6~, tuy nhiên mình lại sinh giới hạn lên đến ~2^{20}~. Sau khi cập nhật bộ test mọi submissions đã được rejudge. Thành thật xin lỗi các bạn vì sự cố này :(.