2021牛客暑期多校训练营7

I

题意

给定x和s，你需要计算有多少个y满足

思路

分解成二进制形式然后逐位考虑

坑点：正整数 位运算优先级

solution

#include <bits/stdc++.h>
#define sc(x) scanf("%lld", &(x))
#define pr(x) printf("%lld\n", (x))
#define rep(i, l, r) for (int i = l; i <= r; ++i)
using namespace std;
typedef long long ll;
const int N = 1e5 + 7;
const int mod = 1e9 + 7;
bool binx[35], bins[35];
int div(ll x, bool d[]) {
    int len = 0;
    while (x) {
        d[++len] = x % 2;
        x /= 2;
    }
    return len;
}
signed main() {
    ll x, s, y;
    sc(x), sc(s);
    int lenx = div(x, binx);
    int lens = div(s, bins);
    ll ans = 1;
    rep(i, 1, lenx) {
        if (binx[i] && !bins[i])
            return puts("0"), 0;
        else if (binx[i] && bins[i])
            ans *= 2;
    }
    if ((x | 0) == s) --ans;
    pr(ans);
    return 0;
}

H

题意

有一个长度为n的数列，他想知道有多少个三元组满足

思路

1. 首先桶一下
2. 然后单独处理1的数量，因为
3. 然后考虑1和其他任意元素的组合，因为
4. 然后开始从2考虑，暴力即可

solution

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 7;
int n;
ll a[N];
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n;
    for (int i = 1, x; i <= n; ++i) cin >> x, ++a[x];

    ll ans = a[1] * a[1] * a[1];
    if (a[1])
        for (int i = 2; i < N; ++i) ans += a[1] * a[i] * a[i] * 2;

    for (ll i = 2; i < N; ++i)
        if (a[i]) {
            if (i * i >= N) break;
            ans += a[i] * a[i] * a[i * i];
            for (ll j = i + 1, x; j < N; ++j)
                if (a[j]) {
                    x = i * j;
                    if (x >= N) break;
                    if (a[x]) ans += a[i] * a[j] * a[x] * 2;
                }
        }
    cout << ans << '\n';
    return 0;
}