โปรแกรม C++ หาค่าสุดท้ายของเมทริกซ์ภายใต้เงื่อนไขความต่างสัมบูรณ์

กำหนดอาร์เรย์ A ขนาด N ค่าเป็น 1,2,3 เท่านั้น สร้างเมทริกซ์ X โดย X[1][j] = A[j] และ X[i][j] = |X[i-1][j] - X[i-1][j+1]| สำหรับ i=2..N, j=1..N+1-i หา X[N][1] (ค่าสุดท้าย)

ตัวอย่าง: A=[1,2,3,1] ผลลัพธ์: 1

ขั้นตอนการแก้ปัญหา (Combinatorial / Lucas Theorem)

1. แปลงปัญหา: คำนวณ arr[i] = |A[i+1] - A[i]| (ขนาด N-1)
2. คำตอบขึ้นอยู่กับ parity ของ binomial coefficients: ใช้ฟังก์ชัน calc(N,M) คำนวณ C(N,M) mod 2 (โดยนับเลข 1 ใน binary)
3. แยกกรณี arr[i] == 1 และ arr[i] == 2 คำนวณ XOR ตามสูตร
4. คืนค่า "1" หรือ "0"

ตัวอย่างโค้ด 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 + 1);
    for (int i = 1; i < n; i++) arr[i-1] = abs(A[i] - A[i-1]);
    --n;
    bool hh = 1, pd = 0, ck = 0;
    for (int i = 0; i < n; i++) if (arr[i]) {
        if (arr[i] == 1) hh = 0, pd ^= calc(n-1, i);
        else ck ^= calc(n-1, i);
    }
    ck &= hh;
    if (pd ^ ck) return "1" + hh;
    return "0";
}

int main() {
    vector<int> A = {1, 2, 3, 1};
    cout << solve(A) << endl;
}

อินพุต / เอาต์พุต

Input: {1, 2, 3, 1}

Output: 1