「题解」Not Quite Lee
link
首先拿到题还是要推一下这个连续整数序列的性质。发现 \(sum_i=b_i-1+2k\)（\(k\in \mathrm{N}\)）。则对于子序列 \(b_i\)，若存在序列 \(\{k\}\)，\(\sum \frac {b_i*(b_i-1)} {2}+b_ik_i=0\)，那么 \(\{b\}\) 是合法的，求方案数。
肯定地，看见要控制这个 \(\{k\}\)，自然想到裴蜀定理。即 \(\gcd{\{b\}}|\sum \frac {b_i*(b_i-1)} {2}\)。这种时候有些伞兵（比如我）就会想到将问题一般化（即枚举因数啊当成一般性问题来做）。但其实既然出题人给了你这么一个结构，你就需要将其 特殊化看待。
回到这道题，发现如果右边没有除以 \(2\)，那么此条件一定满足。换句话说，我们不需要考虑不为 \(2\) 的其他因子，因为除以 \(2\) 也不能对其造成什么影响。（Feature 1）
另外，由于 \(b_i(b_i-1)\) 的特殊结构，也根据 Feature 1，考虑 \(b_i\) 为奇数的时候条件是一定满足的。
考虑 \(k\) 为最大的整数满足 \(2^k|\gcd\)，那么右侧必会出现许多 \(2^{k-1}*(...)\)，所以自然的想到这样的数有偶数个。所以枚举这个 \(k\)，进行组合数计算即可。令恰好有 \(k\) 个 \(2\) 这个因子的的有 \(p\) 个，\(2^{k+1}|b_i(a_i)\) 的有 \(pr\) 个，那么答案增加 \(\sum_{i=2,2|i}^p\binom p i*2^{pr}\)，即 \((2^{p-1}-1)2^{pr}\)。
这也为子序列个数的研究提供了很好的方向：找到特定条件，用组合数计算。
#include
#include
#include
#include
#define LL long long
using namespace std;
const int MAXN = 2e5 + 5, Mod = 1e9 + 7;
int n, a[MAXN], c[MAXN], p[MAXN];
LL ans, all, jc[MAXN], inv[MAXN];
LL C(int x, int y) {
if(x < 0 || y < 0 || x < y) return 0;
return jc[x] * inv[y] % Mod * inv[x - y] % Mod;
}
LL Qpow(LL x, int y) {
LL ans = 1;
for(; y; y >>= 1) {
if(y & 1) ans = ans * x % Mod;
x = x * x % Mod;
}
return ans;
}
int main() {
scanf("%d", &n); jc[0] = 1;
for(int i = 1; i <= n; i ++) jc[i] = jc[i - 1] * i % Mod;
inv[n] = Qpow(jc[n], Mod - 2);
for(int i = n - 1; i >= 0; i --) inv[i] = inv[i + 1] * (i + 1) % Mod;
for(int i = 1; i <= n; i ++) scanf("%d", &a[i]);
for(int i = 1; i <= n; i ++) {
while(a[i] % 2 == 0) a[i] /= 2, c[i] ++;
p[c[i]] ++;
}
for(int i = 0; i <= 30; i ++) {
// 特殊情况 i = 0
// 2的幂恰好有 i个的选偶数个
int pr = 0; all = 0;
for(int j = i + 1; j <= 30; j ++) pr += p[j];
if(!i) {
ans = (ans + (Qpow(2, p[i]) - 1) * Qpow(2, pr)) % Mod; continue;
}
for(int j = 1; j <= p[i] / 2; j ++) all = (all + C(p[i], j * 2)) % Mod;
ans = (ans + all * Qpow(2, pr) % Mod) % Mod;
}
printf("%lld", ans);
return 0;
}