BZOJ4903: [Ctsc2017]吉夫特

传送门
可以发现，(inom{n}{m}equiv 1(mod~2)) 当且仅当 (m~and~n~=~m)
即 (m) 二进制下为 (n) 的子集
那么可以直接写一个 (3^{18}) 的枚举子集 (DP)
但是还有一个 (6^9) 的做法
把数字分成前 (9) 位和后 (9) 位
设 (f(s_1,s_2)) 表示前 (9) 位为 (s_1)，后 (9) 位为 (s_2) 的超集的答案
那么对于一个数 (x)，分成 (x_1,x_2)，转移的时候枚举 (x_1) 的超集，更新的时候枚举 (x_2) 的子集即可

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

const int maxn(1 << 9);
const int mod(1e9 + 7);

inline void Inc(int &x, int y) {
	x = x + y >= mod ? x + y - mod : x + y;
}

int n, f[maxn][maxn], sz = maxn - 1;

int main() {
	register int i, j, v, f1, f2, t, g;
	scanf("%d", &n);
	for (i = 1; i <= n; ++i) {
		scanf("%d", &v), f1 = v >> 9, f2 = v & sz, g = 1;
		for (t = j = sz ^ f1; ; j = (j - 1) & t) {
			Inc(g, f[sz ^ j][f2]);
			if (!j) break;
		}
		for (j = f2; ; j = (j - 1) & f2) {
			Inc(f[f1][j], g);
			if (!j) break;
		}
	}
	for (g = mod - n, i = 0; i <= sz; ++i) Inc(g, f[i][0]);
	printf("%d
", g);
    return 0;
}