CF1610D思路分享（数论，组合计数）

https://codeforces.com/problemset/problem/1610/D

题意概述

一个长度为 \(m\) 的非空数组 \(b\) 被称为“好的”，需要存在 \(m\) 个序列满足以下条件：

1.第 \(i\) 个序列由 \(b_i\) 个连续整数构成。

2.记第 \(i\) 个序列所有元素的和为 \(sum_i\)，\(\sum{sum_i} = 0\)。

给定数组 \(a\)，求出其所有子序列中“好的”子序列的个数，模 \(10^9+7\)。

思路

思考“好的”数组的本质。

令第 \(i\) 个序列元素分别为 \(x_i,x_i+1, \cdots ,x_i+b_i-1\)，则 \(sum_i = b_i \cdot (2x + b_i -1)\)。

那么：

\[\sum{b_i \cdot (2x + b_i - 1)} = 0 \]

展开得到：

\[\frac{\sum{b_i \cdot (b_i-1)}}{2} = -\sum{x_i \cdot b_i} \]

由裴蜀定理可知，方程有解的条件为：

\[\gcd(b_i) \mid \frac{\sum{b_i \cdot (b_i-1)}}{2} \]

令 $p \cdot \gcd(b_i) = \frac{\sum{b_i \cdot (b_i-1)}}{2} $，则 \(2p = \frac{\sum{b_i \cdot (b_i-1)}}{\gcd(b_i)}\)，即：

\[2 \mid \frac{\sum{b_i \cdot (b_i-1)}}{\gcd(b_i)} \]

在模 \(2\) 意义下，考虑如下代换：

\[\gcd(b_i) = 2^t \cdot (2k+1) \]

\[c_i = \frac{b_i}{2^t} \]

那么原式为：

\[2 \mid \frac{\sum{2^t c_i \cdot (2^t c_i - 1)}}{2^t \cdot (2k+1)} \]

即：

\[2\mid \sum{c_i \cdot (2^t c_i - 1)} \]

当 \(t = 0\) 时，显然成立。

当 \(t \ne 0\) 时，\(2 \mid \sum{c_i}\)

接下来需要思考 \(t\) 的本质。

当 \(t = 0\) 时

$ \gcd(b_i) = 2k+1 $，也就是 \(b_i\) 中存在至少一个奇数，故方案的组成为：在所有为奇数的 \(b_i\) 中选择至少一个元素，为偶数的 \(b_i\) 任意选。

当 $t \ne 0 $ 时

由算数基本定理可知，\(b_i\) 可以被分解成 \(2^{t_i} \cdot (2k_i + 1)\) 形式，且这样的形式唯一。那么代换中的 \(t\) 显然是所有 \(t_i\) 中的最小值，也就是：

\[c_i = \frac{b_i}{2^t} = \frac{2^q \cdot b_i}{2^{t_i}} \]

其中 \(q = t_i - t\)。

可见，当 \(t_i > t\) 时，\(c_i\) 为偶数。直观的理解一下：如果 \(t_i > t\)，那么当 \(b_i\) 被分解出 \(t\) 这个因数的时候，它仍然还有一部分因数，这部分因数为偶数（因为当剩下因数为奇数的时候，一定对应它唯一的分解形式，也就是分解到 \(t_i\) 了，但是我们的前提是 \(t_i > t\)）。

所以当 \(t_i > t\) 时，\(c_i\) 为偶数；\(t_i = t\) 时，\(c_i\) 为奇数。

回想一下数组为“好的”的条件，我们需要所有 \(c_i\) 的和为偶数，那么选择方案的组成为：在所有 \(t_i = t\) 的数中选择偶数个元素，\(t_i > t\) 的数中任意选。

实现

预处理所有元素的 \(t_i\)，记录到 \(cnt\) 中，\(cnt_i\) 表示 \(t_i = i\) 的元素数量。同时记录后缀和数组 \(suf\)。

对于 \(t = 0\) 的情况，从 \(cnt_0\) 中选至少一个元素的方案数为 \(2^{cnt_0} - 1\)，其他数任选的方案数为 \(2^{suf_1}\) 。

对于 \(t \ne 0\) 的情况，枚举所有 \(t\)，在 \(t_i = t\) 的数中选偶数个（至少两个），方案数为 \(2^{cnt_t-1} - 1\)，在 \(t_i > t\) 的数中任意选，方案数为 \(2^{suf_{i+1}}\)。

最后解释一下在 \(n\) 个数中选偶数个元素的方案数为 \(2^n\) 的原因：对于集合中任意一个元素 \(x\)，如果选择了它，剩下需要在 \(n-1\) 个元素中选择奇数个元素；如果不选择它，剩下需要在 \(n-1\) 个元素中选择偶数个元素。这两种贡献是取并的，也就是在 \(n-1\) 个元素中选奇数个元素和偶数个元素的并，即在 \(n-1\) 个元素中任选。但要注意选 \(0\) 个元素也被包含在内。

//author:kzssCCC#include <bits/stdc++.h>
using namespace std;
using ll = long long;const int MOD = 1e9+7;ll qpow(ll a,ll b){ll res = 1;while (b){if (b&1){res = res*a%MOD;}a = a*a%MOD;b >>= 1;}return res;
}void solve(){int n;cin >> n;vector<int> a(n+1);for (int i=1;i<=n;i++){cin >> a[i];}vector<int> cnt(32);for (int i=1;i<=n;i++){for (int j=0;j<32;j++){if (a[i]%(1<<j)==0 && (a[i]/(1<<j))&1){cnt[j]++;break;				}}}vector<int> suf(33);for (int i=31;i>=0;i--){suf[i] = suf[i+1]+cnt[i];}ll res = 0;for (int i=1;i<32;i++){if (cnt[i]<2) continue;ll cur = (qpow(2,cnt[i]-1)-1+MOD)%MOD*qpow(2,suf[i+1])%MOD;res = (res+cur)%MOD;}ll add = (qpow(2,cnt[0])-1+MOD)%MOD*qpow(2,suf[1])%MOD;res = (res+add)%MOD;cout << res << '\n';
}int main(){ios::sync_with_stdio(false);cin.tie(0);int t = 1;// cin >> t;while (t--) solve();return 0;
}