T1

求 的方案数，

• 考虑从高到低按位填数
• 考虑
  • 对于 ，当且仅当 是奇数且这一位全填 ，方案数即为 ；
  • 对于 ，当且仅当这一位不全为 且 的个数为偶数，方案数 ；
  • 所以 的方案数为 。
• 考虑 ，当且仅当二进制高位相等，且第 位 ，即 是偶数且全填 ，低位可以任意填，方案数为 ，故总方案数为
• 综上所述
  • 为奇数时答案为
  • 为偶数时答案为
  
• 时间复杂度 ，不过题目放 的做法过。

#include <bits/stdc++.h>
using namespace std;
const int P = 1e9 + 7;
using ll = int64_t;
int n, k;
int fpow(ll a, ll b, ll x = 1) {
    b %= P - 1;
    for (; b; b >>= 1, a = a * a % P)
        if (b & 1)
            x = x * a % P;
    return x;
}
int main() {
    scanf("%d%d", &n, &k);
    int q = fpow(2, n - 1) + (n & 1 ? 1 : -1), qk = fpow(q, k), ans = qk;
    if (n % 2 == 0) {
        int pn = fpow(2, n);
        ans = (ans + fpow(q - pn + P, P - 2, qk - fpow(pn, k) + P)) % P;
    }
    printf("%d\n", ans);
}

T2

最大化 ，将序列 分为不超过 个非空段， 表示 属于第几段（从 开始），

• 化简式子

  

• 所以答案就是 ，求出前缀和排序或者用堆维护即可。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
using ll = int64_t;
int n, k;
int main() {
    scanf("%d%d", &n, &k);
    vector<int> a(n), b(n), s(n);
    string str(n, 0);
    for (auto &x : a) scanf("%d", &x);
    scanf("%s", str.data());
    ll ans1 = 0, ans2 = 0, sn = 0, sum_s = 0;
    priority_queue<int> q;
    for (int i = 0; i < n; ++i) {
        int val = str[i] == '1' ? 1 : -1;
        ans1 += a[i] * val;
        s[i] = (i ? s[i - 1] : 0) + val;
    }
    ans2 = sn = s[n - 1];
    nth_element(s.begin(), s.begin() + k, s.end());
    sort(s.begin(), s.begin() + k);
    for (int i = 0; i < k; ++i) {
        sum_s += s[i];
        ans2 = max(ans2, i * sn - sum_s);
    }
    printf("%lld\n", ans1 + ans2);
    return 0;
}

T3

定义 ，其余情况为 。求

• 求前缀和 ，统计 的出现次数，求 即可。注意 要枚举到 ， 。

#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 5, M = 50;
using ll = int64_t;
ll pw[M];
void solve() {
    int n;
    scanf("%d", &n);
    unordered_map<ll, int> cnt = {{0, 1}};
    ll sum = 0, ans = 0;
    for (int i = 0, x; i < n; ++i) {
        scanf("%d", &x), ++cnt[sum += x];
        for (int j = 1; j < M; ++j)
            if (cnt.count(sum - pw[j]))
                ans += (ll)cnt[sum - pw[j]] * j;
    }
    printf("%lld\n", ans);
}
int main() {
    pw[0] = 1;
    for (ll i = 1; i < M; ++i)
        pw[i] = pw[i - 1] << 1;
    int t;
    scanf("%d", &t);
    while (t--) solve();
    return 0;
}