HDU 4810 Wall Painting — 組合數學 + 異或性質按位計算

問題描述

給定 n 個數，對每個 day = 1..n，從中選 day 個數，計算所有選法的異或和，再求和。結果模 1,000,003。n ≤ 1000。

核心思路：按位獨立計算

異或運算各位獨立。對第 i 位（權值 2^i），設數組中有 c1 個數該位為 1，c0 = n - c1 個為 0。選 day 個數使該位異或為 1，等價於選奇數個 1。方案數：

Σ_{奇數 j} C(c1, j) * C(c0, day - j)

該位貢獻 = 方案數 × 2^i。累加所有位得答案。

預處理

• 組合數 C[n][k] mod MOD，n ≤ 1000 用帕斯卡三角 O(n²) 預處理。
• 2 的冪次 mi[i] = 2^i mod MOD。
• 統計每位 1 的個數 sum[i]。

參考代碼 (C++)

#include <cstdio>
#include <cstring>
const long long MOD = 1000003;
const int N = 1005;
int n, num, sum[32];
long long C[N][N], mi[32];

void tra(int num) {
    int sn = 0;
    while (num) { sum[sn++] += num & 1; num >>= 1; }
}

long long cal(int day) {
    long long ans = 0;
    for (int i = 0; i < 32; ++i) {
        for (int j = 1; j <= day && j <= sum[i]; j += 2) {
            if (sum[i] < j || n - sum[i] < day - j) continue;
            ans = (ans + C[sum[i]][j] * C[n - sum[i]][day - j] % MOD * mi[i]) % MOD;
        }
    }
    return ans;
}

int main() {
    mi[0] = 1;
    for (int i = 1; i < 32; ++i) mi[i] = mi[i-1] * 2 % MOD;
    for (int i = 0; i < N; ++i) {
        C[i][0] = C[i][i] = 1;
        for (int j = 1; j < i; ++j) C[i][j] = (C[i-1][j] + C[i-1][j-1]) % MOD;
    }
    while (~scanf("%d", &n)) {
        memset(sum, 0, sizeof(sum));
        for (int i = 0; i < n; ++i) { scanf("%d", &num); tra(num); }
        for (int i = 1; i < n; ++i) printf("%lld ", cal(i));
        printf("%lld\n", cal(n));
    }
    return 0;
}

複雜度

• 預處理：O(N² + 32)。
• 每查詢：O(32 × day)，總 O(n²) 可接受。

總結

本題展示了「異或按位分解 + 組合計數」的經典套路。關鍵洞察：異或運算各位獨立，選擇奇數個 1 使該位結果為 1，利用乘法原理與加法原理組合計數。