自动搬运

查看原文

来自洛谷，原作者为

	_ctz Ádigie šos ök iroг.

搬运于2025-08-24 21:52:33，当前版本为作者最后更新于2019-10-10 15:20:10，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

安利blog

传送门

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

卢卡斯搞那一坨组合数：

$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);
}