传送门

我好菜啊连卢卡斯都不会了

卢卡斯搞那一坨组合数：

$C_{a_i}^{a_j}\equiv C_{a_i/2}^{a_j/2}\times C_{a_i\%2}^{a_j\%2}\pmod 2$

后面那个$C_{a_i\%2}^{a_j\%2}$有四种情况$C_0^0,C_0^1,C_1^0,C_1^1$，其中只有$C_0^1=0$。

然后继续处理$C_{a_i/2}^{a_j/2}$。

我们发现，这就是把$a_i$和$a_j$按二进制拆位了。其中只要出现过$C_0^1$，$C_{a_i}^{a_j}$就等于$0$。

也就是说二进制下不存在某一位$a_i$为$0$而$a_j$为$1$，即$a_j$二进制下是$a_i$的子集。

问题就变成了求子序列的个数，满足每一项在二进制下是前一项的子集。

$a_i\le 233333$还互不相同，直接设$f(i)$为以$i$为结尾的子序列个数，枚举子集刷表转移就没了。

而且都是它的子集了，就不用考虑序列的单调性了。

复杂度是枚举子集的$O(3^{\log_2\max\{a_i\}})$。

非常简短的代码：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>

#define maxn 250005
#define inf 0x3f3f3f3f

const int mod = 1e9 + 7;

using namespace std;

inline int read(){
    int x=0,y=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')y=1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return y?-x:x;
}
int f[maxn];
int main(){
    int n=read(),a,ans=0;
    for(register int i=1;i<=n;++i){
        a=read();
        for(register int S=a-1&a;S;S=S-1&a)(f[S]+=f[a]+1)%=mod;
        (ans+=f[a])%=mod;
    }
    printf("%d\n",ans);
}