[题解]CF1610D-Not Quite Lee

Posted on 2021-11-24 Edited on 2022-01-13 In -题解

经典我是傻逼环节.

题意

给出长度为$n$的数组$A = \{a_i\}$, $1 \leq n \leq 2 \cdot 10^5,1 \leq a_i \leq 10^9$.

对于$A$的任意长度为$m$的非空子序列$B = \{b_1,b_2,..,b_m\}$, 定义$f(b_i,k_i) = \sum_{j = 0}^{b_i} (j + k_i)$, 其中$k_i$为任意整数. 一个子序列$B$合法当且仅当 $ {k_i} |_{i = 1}^mf(b_i,k_i) = 0$.

求$A$中全部合法子序列数量模$10^9+7$.

题解

首先我们考虑如何判断某个序列是否合法. 有$f(b_i,k_i) = \frac{b_i\cdot(b_i + 1)}{2} + k_i\cdot b_i$, 那么$\sum_{i = 1}^mf(b_i,k_i) = 0$可以转化为$\sum_{i = 0}^m{\frac{b_i\cdot (b_i + 1)}{2}} = \sum_{i = 0}^m k_i \cdot b_i$. 这是一个一次不定方程. 设$g = gcd(b_1,b_2,...,b_m)$, 当且仅当$g | \sum_{i = 0}^m \frac{b_i \cdot (b_i+1)}{2}$时有整数解.

手画一下几组样例可以看出, 当序列中存在奇数时必定合法. 当序列中存在至少一个奇数时, 显然$g$也是奇数. 那么对于每个$\frac{b_i \cdot (b_i + 1)}{2}$, 如果$b_i$是偶数有$g | \frac{b_i}{2}$, 否则有$g|(b_i + 1)$ 且$\frac{b_i}{2}$为整数. 因而序列中存在奇数时必有$g | \sum_{i = 0}^m \frac{b_i \cdot (b_i+1)}{2}$.

设$A$中奇数个数为$odd$, 这一部分对答案的贡献为$(2^{odd} - 1) \cdot 2^{n-odd}$

现在考虑序列中全为偶数的情况. 设$h$是最大的使得$2^h | g$的非负整数. 我们可以把$g$拆分为$g' \cdot 2^h$. 显然$g'$为奇数. 根据上一段的讨论, 有$g' | \sum_{i = 0}^m \frac{b_i \cdot (b_i + 1)}{2}$. 因而全为偶数的序列是否合法取决于$2^h$能否整除$\sum_{i = 0}^m \frac{b_i \cdot (b_i + 1)}{2}$. 对于每个$b_i$, 设$l$是最大的使得$2^l|b_i$的非负整数. $l$可以分三种情况来讨论:

$l > h$.

此时有$2^h | \frac{b_i}{2}$, 所以$2^h | \frac{b_i \cdot(b_i + 1)}{2}$.
$l = h$.

此时$2^h \nmid \frac{b_i}{2}$且$b_i + 1$是奇数, 因此$2^h \nmid \frac{b_i \cdot(b_i + 1)}{2}$. 由于$\frac{b_i \cdot(b_i + 1)}{2 \cdot g'} \mod 2^h = 2^{h-1}$, 如果这种情况下的$b_i$个数有偶数个, 那它们的和仍然可以被$2^h$整除.
$l < h$. 由于$g \geq 2^h$, 不可能存在这种情况.

综上可知, 当序列中全为偶数时, 按能被$2^l$整除的最大$l$来对$b_i$分类, 当且仅当$l$最小那组的个数为偶数时序列合法. 在统计时可以枚举最小的$l$.

总时间复杂度$n \log (\max\{a_i\})$

代码

//
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int long long
#define endl '\n'
mt19937 Rand(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = 2e5+10;//CHANGE IT!
const int maxm = maxn*2;
const int p = 1e9+7;//CHANGE IT!
ll fac[maxn],cnt[maxn];
ll Pow(ll x,ll d,ll p = p){ll ta=1;if(d==0)return 1%p;x %= p;ll a=Pow(x,d/2,p);ta=a*a%p;if(d%2)ta=ta*x%p;return ta%p;}
ll C(ll n,ll m){
	if(m > n)return 0;
	return (fac[n]*Pow(fac[m],p-2)%p*Pow(fac[n-m],p-2)%p)%p;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.setf(ios::fixed,ios::floatfield);
	cout.precision(12);	 
	fac[0] = 1;
	for(int i = 1;i < maxn;i++)fac[i] = fac[i-1]*i%p;
	int n;
	cin >> n;
	int odd = 0;
	for(int i = 1;i <= n;i++){
		int x;
		cin >> x;
		if(x&1)odd++;
		else{
			int qwq = 0;
			while(x%2 == 0)qwq++,x /= 2;
			cnt[qwq+1]++;
		}
	}
	ll ans = (Pow(2,odd) - 1 + p)%p*(Pow(2,n - odd)) % p;
	ll res = n - odd;
	for(int k = 1;k <= 32;k++)if(cnt[k]){
		ll tmp = 0;
		res -= cnt[k];
		ans = (ans + (Pow(2,cnt[k] - 1) - 1 + p)%p * Pow(2,res) % p) % p;
	}
	cout << ans;
	return 0;
}