题目描述
简单的题目，既是礼物，也是毒药。
B 君设计了一道简单的题目，准备作为 gift 送给大家。
输入一个长度为 $ n $ 的数列 $ a_1, a_2 , \dots, a_n $ 问有多少个长度大于等于 $ 2 $ 的不上升的子序列 $ a_{b_1}, a_{b_2}, \ldots, a_{b_k} $ 满足
$$ \prod\limits_{i = 2} ^ k \binom{a_{b_{i – 1}}}{a_{b_i}} \bmod 2 = \binom{a_{b_1}}{a_{b_2}} \times \binom{a_{b_2}}{a_{b_3}} \times \cdots \times \binom{a_{b_{k – 1}}}{a_{b_k}}\bmod 2 > 0 $$
输出这个个数对 $ 1000000007 $ 取模的结果。
G 君看到题目后，为大家解释了一些基本概念。
我们选择任意多个整数 $ b_i $ 满足
$$ 1 \leq b_1 < b_2 < \cdots < b_{k – 1} < b_k \leq n $$
我们称 $ a_{b_1}, a_{b_2}, \ldots, a_{b_k} $ 是 $ a $ 的一个子序列。
如果这个子序列同时还满足
$$ a_{b_1} \geq a_{b_2} \geq \ldots \geq a_{b_k} $$
我们称这个子序列是不上升的。
组合数 $ \binom{n}{m} $ 是从 $ n $ 个互不相同的元素中取 $ m $ 个元素的方案数，具体计算方法如下：
$$ \binom{n}{m} = \frac{n!}{m!(n – m)!} = \frac{n \times (n – 1) \times \cdots \times 2 \times 1}{(m \times (m – 1) \times \cdots \times 2 \times 1)((n – m) \times (n – m – 1) \times \cdots \times 2 \times 1)} $$
这里要特别注意，因为我们只考虑不上升子序列，所以在求组合数的过程中，一定满足 $ n \geq m $，也就是 $ \binom{a_{b_{i – 1}}}{a_{b_i}} $ 中一定有 $ a_{b_{i – 1}} \geq a_{b_i} $。
我们在这里强调取模 $ x \bmod y $ 的定义：
$$ x \bmod y = x – \lfloor \frac{x}{y} \rfloor \times y $$
其中 $ \lfloor n \rfloor $ 表示小于等于 $ n $ 的最大整数。
$ x \bmod 2 > 0 $，就是在说 $ x $ 是奇数。
与此同时，经验告诉我们一个长度为 $ n $ 的序列，子序列个数有 $ O(2 ^ n) $ 个，所以我们通过对答案取模来避免输出过大。
B 君觉得 G 君说的十分有道理，于是再次强调了这些基本概念。
最后，G 君听说这个题是作为 gift 送给大家，她有一句忠告。
“Vorsicht, Gift!”
‘‘小心. . . . . . 剧毒!”
精简题面
思路
代码
#include<cstdio>
typedef long long ll;
ll n,a,x,i,f[233334],m=1e9+7;
int main(){
scanf("%lld",&n);
while(n--){
scanf("%lld",&x);
for (i=x;i<233334;i=i+1|x)
f[x]+=f[i];
(a+=f[x]++)%=m;
f[x]%=m;
}
printf("%lld\n",a);
return 0;
}