題意 ：

• 給一序列，設(shè)元素和為sum，求有幾個子序列滿足子序列的元素和為sum - 1

思路 ：

• 1個元素1可以使得子序列元素和為原序列元素和-1，所以方案數(shù)與1的個數(shù)有關(guān)，且線性相關(guān)，元素0可有可無，所以方案數(shù)還要乘上$2^{cn{t}_0}$
• 所以答案是$cn{t}_1?2^{cn{t}_0}$，記得開long long

#include <iostream> #include <algorithm>using namespace std;typedef long long ll;ll qmi(ll a, ll b) {ll res = 1;while (b){if (b & 1) res = res * a;a = a * a;b >>= 1;}return res; }int main() {ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);int _;cin >> _;while (_ -- ){int n;cin >> n;ll cnt0 = 0, cnt1 = 0;for (int i = 1; i <= n; i ++ ){int x;cin >> x;if (x == 0) cnt0 ++ ;if (x == 1) cnt1 ++ ;}cout << cnt1 * qmi(2ll, cnt0) << endl;}return 0; }

總結(jié)

以上是生活随笔為你收集整理的Luntik and Subsequences 思维的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。