Chương trình C++ tìm giá trị cuối cùng của ma trận chênh lệch tuyệt đối

Mô tả bài toán

Cho mảng A kích thước N (giá trị 1,2,3). Xây ma trận X: hàng 1 là A, hàng cột = |X[i-1][j] - X[i-1][j+1]|. Tìm X[N][1].

Ví dụ

A=[1,2,3,1]. Đầu ra: 1.

Thuật toán (Tổ hợp + XOR parity)

1. Biến đổi mảng thành arr[i]=|A[i+1]-A[i]|| (giá trị 0,1,2).
2. Giá trị cuối = XOR của các hệ số nhị phân của tổ hợp C(n-1, i) modulo 2.
3. Hàm calc(N,M) tính parity của C(N,M) bằng cách đếm bit 1 trong biểu diễn nhị phân (Lucas theorem).
4. Xử lý riêng các giá trị 1 và 2 trong arr.

Đoạn mã C++

#include <bits/stdc++.h>
using namespace std;

int calc(int N,int M){
    int cnt=0;
    for(int k=N;k;k>>=1) cnt+=k>>1;
    for(int k=M;k;k>>=1) cnt-=k>>1;
    for(int k=N-M;k;k>>=1) cnt-=k>>1;
    return !cnt;
}

string solve(vector<int> A){
    int n=A.size();
    vector<int> arr(n);
    for(int i=1;i