就差一个0啊……

· · 题解

P15078 题解

思路

奇妙数学题。赛时因为忘了 0 而没 A，属实可惜。

我们发现，两个数操作的值不可能会与“第三个数”有关。

所以我们只用关注相邻两个数的各种运算的结果。

我们设：

我们可以发现，所有的结果均可以由以下三个数得到：

为啥呢？这个其实也比较好想，把所有的数拆成 2 进制，就只有这些数任意一个里面包含 1 的位才会有 1，其他必定是 0。

那我们可以在这三个数里面选几个进行或运算（因为每一个数都能通过一些方法变成 0），可行的结果有：

把这些数装进一个 set 或 map 中去重就可以得到答案了。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n;
int a[100010];
map<int,int> mp;
signed main() {
    mp[0]++;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<n;i++){
        int ai=a[i];
        int aj=a[i+1];
        mp[ai]++;
        mp[aj]++;
        mp[ai&aj]++;
        mp[ai|aj]++;
        mp[ai^aj]++;
        mp[ai^(ai&aj)]++;
        mp[aj^(ai&aj)]++;
    }
    cout<<mp.size()<<endl;
    return 0;
}

ヾ(•ω•`)o