P3773 [CTSC2017]吉夫特

发现只要式子中有一个数为奇数，整个式子就为 \(0\)。

把膜数代到每一乘积项中，容易发现这个东西就是一个 \(\text{Lucas}\) 定理。

卢卡斯定理有一个性质，那就是如果膜数是 \(p\)，那么使用 \(\text{Lucas}\) 定理就和 \(p\) 进制数类似。

递归展开 \(\text{Lucas}\) 就容易发现对于 \({n \choose m}\)，如果出现 \(n = 0，m = 1\) 即 \({ 0 \choose 1 }\) 的情况，那么这个式子就是 \(0\) 了。

根据 \(\text{Lucas}\) 定理 \(p\) 进制数的性质，直接位运算 \(n | m\) 即可判断一个组合数是否为奇数。

然后仿照最长上升子序列这样的问题写个 \(dp\) 转移就行了，转移就是枚举子集，因为转移条件是或运算，复杂度是 \(O(3^n)\) 证明大概就是二项式定理整整就出来了。

代码放一下，免得以后忘了枚举子集怎么写。

#include <cstdio>
#include <algorithm>
#include <cstring>

using std::max;

typedef long long ll;

const int MAXN = 211985 + 5;
const int MAXA = 233333 + 5;
const int MOD = 1e9 + 7;

int n, a[MAXN << 1];
int id[MAXA << 1];
ll f[MAXA << 1];

int main() {

    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);
        id[ a[i] ] = i;
    }
    ll ans = 0;
    for (int i = 1; i <= n; ++i) {
        for (int s = (a[i] - 1) & a[i]; s; s = (s - 1) & a[i]) {
            if (id[s] > i) {
                f[s] = (f[s] + f[ a[i] ] + 1) % MOD;
            }
        }
        ans = (ans + f[ a[i] ]) % MOD;
    }
    printf("%lld\n", ans);

    return 0;
}