【CTSC2017】吉夫特

UOJ 300

题目大意

给出大小为 (n) 的两两互异的数组 (a) ，问有多少个不下降子序列满足 (prod_{i=2}^k binom{a_{k-1}}{a_k} ; mod ; 2 > 0) ，答案模 (1000000007)

数据范围

(1 le n le 211985,1 le a_i le 233333)

时空限制

2s,512MB

分析

由于模 (2) 的性质，我们要保证每个组合数都是奇数，这时我们想到与组合数有关的卢卡斯定理，得到
[ binom {x}{y} ; mod ; 2 = binom {lfloor dfrac x2 rfloor}{lfloor dfrac y2 rfloor} times binom {x ; mod ; 2}{y ; mod ; 2} ]
发现这就是对于二进制的每一位考虑是否满足，不能出现 (binom 01) ，也就是 (x) 是 (y) 的超集，由于 (a) 互异，所以我们直接枚举超集转移即可，因为 (a_i) 互不相等，所以时间为 $O(3^n) $

Code

#include <cstdio>
#include <iostream>
using namespace std;
inline char nc() {
    static char buf[100000],*l = buf,*r = buf;
    return l==r&&(r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++;
}
template<class T> void read(T & x) {
    x = 0; int f = 1,ch = nc();
    while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=nc();}
    while(ch>=‘0‘&&ch<=‘9‘){x=x*10-‘0‘+ch;ch=nc();}
    x *= f;
}
const int maxn = 211985 + 5;
const int maxa = 233333 + 5;
const int mod = 1000000007;
int n,m,a[maxn];
int f[maxa];
inline void add(int & x,int y) {
    x += y;
    if(x >= mod) x -= mod;
}
int solve() {
    int re = 0;
    for(int i = 1; i <= n; ++i) {
        int x = a[i];
        for(int j = (x + 1) | x; j <= m; j = (j + 1) | x) {
            add(f[x],f[j]);
        }
        add(re,f[x]),add(f[x],1);
    }
    return re;
}
int main() {
//  freopen("testdata.in","r",stdin);
    read(n);
    for(int i = 1; i <= n; ++i) {
        read(a[i]),m = max(m,a[i]);
    }
    printf("%dn",solve());
    return 0;
}