Các lượt nộp
    Danh sách bài
    Trang chủ
    Báo lỗi

    solution

    Đề bài: [Giải thuật] Số đoạn con có XOR bằng K

    Cho dãy nnn số nguyên không âm và số KKK. Hãy đếm số đoạn con liên tiếp [i,j][i, j][i,j] (i≤ji \le ji≤j) có XOR của các phần tử bằng KKK. Dùng tiền tố XOR và bảng băm để đạt O(n)O(n)O(n).

    • Định dạng đầu vào:

      Dòng đầu nnn và KKK. Dòng hai gồm nnn số nguyên không âm.

    • Ràng buộc đầu vào:

      1≤n≤1051 \le n \le 10^51≤n≤105, 0≤K,ai≤1090 \le K, a_i \le 10^90≤K,ai​≤109.

    • Định dạng đầu ra:

      In một số nguyên: số đoạn con thỏa mãn.

    Ví dụ:

    Đầu vào:

    4 6
4 2 2 6

    Đầu ra:

    3

    Giải thích:

    Ba đoạn con có XOR bằng 6: [1,2]=4^2=6, [2,4]=2^2^6=6, và [4,4]=6. Vậy đáp án là 3.

    Đang tải editor...