HDU 4810 Wall Painting(組合數學)

思路：先把每個數字按位分離出來，存放1的個數，那麼每位0的個數為n - 1的個數，然後利用組合數學和異或的原理，枚舉奇數個1的情況，然後利用乘法和加法計數原理累加出來的就是該位的答案，最後乘上改為對應的數值最後加起來就是答案

代碼：

#include 
#include 

const __int64 MOD = 1000003;
const int N = 1005;
int n, num, sum[32];
__int64 C[N][N], mi[32];

void tra(int num) {
	int sn = 0;
	while (num) {
		sum[sn++] += num % 2;
		num /= 2;
 	}
}

__int64 cal(int day) {
	__int64 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) % MOD;
  		}
 	}
 	return ans;
}

int main() {
	mi[0] = 1;
	for (int i = 1; i < 32; i++)
		mi[i] = mi[i - 1] * 2;
	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(%I64d , cal(i));
    	}
    	printf(%I64d
, cal(n));
 	}
	return 0;
}