牛客小白月赛25-J异或和之和——位运算与组合计数

传送门：https://ac.nowcoder.com/acm/contest/5600/J

题意

在一个数组中任取三个数的异或和之和。

异或：二进制下相同为0，不同为1。如： 0 ^ 1 = 1, 0 ^ 1 = 1, 1 ^ 1 = 0, 0 ^ 0 = 0。

在任取三个数中，只有两种情况的异或为1：1 1 1 和 0 0 1 所以一开始就要用一个异或数组来记录每个数二进制下的1的个数。

1
2
3
4
5
6
7
8
9
10
11
12
13
for(int i = 0;i < n; i++)
    {
        ll x;
        cin >> x;
        ll k = 0;
        while(x) // 二进制下的每一位的1储存下来,N-t[i]就是0的个数
        {
            if(x&1)
                XOR[k]++;
            k++;
            x >>= 1;
        }
    }

当在所有1 1 1的情况下有C(XOR[i], 3)种，所有的1里任取3个；在所有0 0 1的情况下有C(n - XOR[i], 2) * XOR[i])种，所有的0里人任取2个在和任意一个1组合。

由于处理组合数时，分子分母很大，需要用到费马小定理

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
##include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

##define INF 0x7f7f7f
##define mem(a,b) memset(a , b , sizeof(a))
##define FOR(i, x, n) for(int i = x;i <= n; i++)
const ll mod = 1e9 + 7;
// const int maxn = 100005;

ll FPM(ll a, ll b)
{
    ll ans = 1;
    while(b)
    {
        if(b & 1)
        {
            ans = ans * a % mod;
        }
        a = a * a % mod;
        b >>= 1;
    }
    return ans % mod;
}

ll C(ll n, ll m)
{
    if(n < m)
        return 0;
    ll ans = 1;
    for(ll i = 1;i <= m; i++)
    {
        ans = (ans % mod * (n - i + 1) % mod * FPM(i, mod - 2) % mod) % mod;
    }
    return ans % mod;
}

ll XOR[64];

void solve()
{
    ll n;
    cin >> n;
    for(int i = 0;i < n; i++)
    {
        ll x;
        cin >> x;
        ll k = 0;
        while(x) // 二进制下的每一位的1储存下来,N-t[i]就是0的个数
        {
            if(x&1)
                XOR[k]++;
            k++;
            x >>= 1;
        }
    }
    ll sum = 0;
    ll k = 1;
    for(ll i = 0;i < 64; i++)
    {
        sum = (sum % mod + k * (C(XOR[i], 3) % mod + XOR[i] % mod * C(n - XOR[i], 2) % mod) % mod) % mod;
        sum %= mod;
        k = (k << 1) % mod;
    }
    cout << sum % mod;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
##ifdef FZT_ACM_LOCAL
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
##else
    ios::sync_with_stdio(false);
    int T = 1;
    //cin >> T;
    while(T--)
        solve();
##endif
    return 0;
}

本文作者：jujimeizuo
本文地址： https://blog.jujimeizuo.cn/2020/05/20/nowcoder-newbie25-j/
本博客所有文章除特别声明外，均采用 CC BY-SA 3.0 协议。转载请注明出处！