Bài toán và phân tích

Bài toán yêu cầu tính giá trị của dãy số: (a_0=-3, a_1=-6, a_2=-12), với công thức truy hồi (a_n=3a_{n-1}+a_{n-2}-3a_{n-3}+3^n). Tìm tổng XOR của (T) giá trị (a_n \mod p).

Phân tích bài toán:

• Có thể sử dụng hai phương pháp chính là ma trận (lũy thừa nhanh) và công thức tổng quát.
• Cả hai cách đều có độ phức tạp (O(\log_2(n))) nhưng ma trận nhân chậm hơn do hệ số lớn.

Độ phức tạp thời gian:

• Ma trận: (O(16T \log_2(n)))
• Công thức tổng quát: (O(T \log_2(n)))

Do (T) có thể lên tới (5e7) và (n) đến (2^{63}-1), cần dùng phương pháp tối ưu hóa như lũy thừa nhanh để giải quyết.

Công thức tổng quát

Công thức tổng quát được suy ra từ: [ a_n - a_{n-2} = 3(a_{n-1} - a_{n-3}) + 3^n ] Sau các bước biến đổi: [ b_n = 3b_{n-1} + 3^n ] [ c_n = c_{n-1} + 1 ]

Kết quả cuối cùng:

• Với (n) chẵn: (a_n = \frac{(4n-13)3^{n+2} + 117}{32} - 3)
• Với (n) lẻ: (a_n = \frac{(4n-13)3^{n+2} + 51}{32})

Mã nguồn thực hiện

Để tối ưu hóa việc tính lũy thừa, ta sử dụng kỹ thuật "lũy thừa nhanh" cho cơ số cố định 3. Mã nguồn dưới đây minh họa cách làm này:

#define Q 32000
long long prePow[Q+1], prePowBatch[Q+1];

// Tiền xử lý
prePow[0] = prePowBatch[0] = 1;
for(int i = 1; i <= Q; ++i) {
    prePow[i] = (prePow[i-1] * 3) % MOD;
}
for(int i = 1; i <= Q; ++i) {
    prePowBatch[i] = (prePowBatch[i-1] * prePow[Q]) % MOD;
}

// Hàm gọi lũy thừa nhanh
long long fastExp(int n) {
    return (prePowBatch[n / Q] * prePow[n % Q]) % MOD;
}

Trong quá trình tính toán, chú ý sử dụng phép lấy mô đun để tránh tràn số nguyên dài.

Mã nguồn hoàn chỉnh

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

const int MOD = 1000000007;
const int INV32 = 281250002;
const int Q = 32000;

long long prePow[Q+1], prePowBatch[Q+1];
int T, result;

void initFastExp() {
    prePow[0] = prePowBatch[0] = 1;
    for(int i = 1; i <= Q; ++i) {
        prePow[i] = (prePow[i-1] * 3) % MOD;
    }
    for(int i = 1; i <= Q; ++i) {
        prePowBatch[i] = (prePowBatch[i-1] * prePow[Q]) % MOD;
    }
}

long long computeValue(unsigned long long x) {
    if(x & 1) {
        return ( ( (36 * (x % MOD) - 117 + MOD) % MOD ) * fastExp(x % (MOD - 1)) + 51 ) % MOD * INV32 % MOD;
    } else {
        return ( ( (36 * (x % MOD) - 117 + MOD) % MOD ) * fastExp(x % (MOD - 1)) + 21 ) % MOD * INV32 % MOD;
    }
}

int main() {
    scanf("%d", &T);
    initFastExp();
    unsigned long long randVal;
    while(T--) {
        scanf("%llu", &randVal);
        result ^= computeValue(randVal);
    }
    printf("%d\n", result);
    return 0;
}