P3773 CTSC2017 吉夫特 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
这个题面非常诈骗，应该是出题者故意的。
题目中那么老长串式子，其实就等价于这个长度为 \(m\) 的子序列需要满足：
这个子序列中，对于每一对相邻的前后项（总共 \(m - 1\) 对），设前项是 \(a\)，后项是 \(b\)，都有：
\[\dbinom{a}{b} \bmod 2 = 1 \]至于不上升的限制，那是假的：如果中途上升，也就是存在 \(a < b\)，显然会有 \(\dbinom{a}{b} = 0\)，已经不满足题目的制约了。
我们考虑使用 Lucas。有：
\[\dbinom{a}{b} \equiv\dbinom{\lfloor\frac{a}{2}\rfloor}{\lfloor\frac{b}{2}\rfloor}\dbinom{a \bmod 2}{b \bmod 2} \pmod 2 \]发现后面的组合数只有四种，分别是 \(\dbinom{0}{0}\)，\(\dbinom{0}{1}\)，\(\dbinom{1}{0}\)，\(\dbinom{1}{1}\)。除了 \(\dbinom{0}{1} = 0\) 以外，剩下的均为 \(1\)。
然后接着对 \(\dbinom{\lfloor\frac{a}{2}\rfloor}{\lfloor\frac{b}{2}\rfloor}\) Lucas。我们发现这不就是在对 \(a\) 和 \(b\) 二进制拆位吗。
换句话说，设 \(a_i\) 表示 \(a\) 的二进制从低到高第 \(i\) 位，那么有：
\[\dbinom{a}{b} \equiv \dbinom{a_0}{b_0}\dbinom{a_1}{b_1} \dbinom {a_2}{b_2} \cdots \pmod 2 \]显然当且仅当中间没出现过 \(\dbinom{0}{1}\) 这一项，整个同余式最后会和 \(1\) 同余。
也就是说，不存在某一位使得 \(a\) 在这一位上是 \(0\) 而 \(b\) 在这一位上是 \(1\)。
想一下，这不就是在说 \(b\) 所有为 \(1\) 的二进制位是 \(a\) 所有为 \(1\) 的二进制位的子集吗。
简单刷表 dp 就可以了。
const int maxa = 250005;
const int mod = (int)1e9 + 7;
int f[maxa];
signed main() {
int n = read(), ans = 0;
for (int i = 1; i <= n; ++i) {
int x = read();
for (int j = (x & (x - 1)); j; j = (x & (j - 1)))
(f[j] += f[x] + 1) %= mod;
(ans += f[x]) %= mod;
}
printf("%lld\n", ans);
return 0;
}