题目传送门

　　戳此处转移

题目大意

　　给定一个长为$n$的序列，问它有多少个长度大于等于2的子序列$b_{1}, b_{2}, \cdots, b_{k}$满足$\prod_{i = 2}^{k}C_{b_{i - 1}}^{b_{i}} \equiv 1 \pmod{2}$。答案模$10^{9} + 7$

 /**

  * uoj

  * Problem#300

  * Accepted

  * Time: 400ms

  * Memory: 2956k

  */

 #include <bits/stdc++.h>

 using namespace std;

 typedef bool boolean;

 const int S =  << , M = 1e9 + ;

 const int maskL = ( << ) - , maskH = maskL << , mask = maskL | maskH;

 int n;

 int *ar;

 int f[S][S];

 inline void init() {

     scanf("%d", &n);

     ar = new int[(n + )];

     for (int i = ; i <= n; i++)

         scanf("%d", ar + i);

 }

 inline int query(int S) {

     int rt = , s0 = S & maskL, s1 = (S & maskH) >> , ms1 = s1 ^ maskL;

     for (int s = ms1; s; s = (s - ) & ms1)

         rt = (rt + f[s | s1][s0]) % M;

     return (rt + f[s1][s0]) % M;

 }

 inline void modify(int S, int val) {

     int s0 = S & maskL, s1 = (S & maskH) >> ;

     for (int s = s0; s; s = (s - ) & s0)

         f[s1][s] = (f[s1][s] + val) % M;

     f[s1][] = (f[s1][] + val) % M;

 }

 int res = ;

 inline void solve() {

     modify(mask, );

     for (int i = , c; i <= n; i++) {

         c = query(ar[i]);

         res = (res + c) % M;

         modify(ar[i], c);

     }

     res = (res - n + M) % M;

     printf("%d", res);

 }

 int main() {

 //    freopen("gift.in", "r", stdin);

     init();

     solve();

     return ;

 }