526互联

Codeforces Round 750 (Div. 2) B. Luntik and Subsequences

发布时间 2023-09-26 17:21:32作者: zsxuan

给一个数组 \(a_1, a_2, \cdots, a_n\) ，定义 \(s = \sum_{i = 1}^{n} a_i\) 。

询问有多少个 \(a\) 的子序列满足 \(\sum a_{i_k} = s - 1\) 。

显然要选出一个 \(1\) 不加入子序列，任意一个 \(0\) 可以加入或不加入子序列。

于是 \(ans = \binom{cnt1}{1} \cdot 2^{cnt0}\) 。

view 
#include <bits/stdc++.h>
void solve() {
	int n; std::cin >> n;
	int cnt1 = 0, cnt0 = 0;
	for (int i = 1, x; i <= n; i++) {
		std::cin >> x;
		cnt1 += (x == 1);
		cnt0 += (x == 0);
	}
	std::cout << 1LL * cnt1 * (1LL << cnt0) << "\n";
}
signed main() {
	int _ = 1; std::cin >> _;
	while (_--) solve();
	return 0;
}