位运算#蓝桥杯

位运算#蓝桥杯

1、小蓝学位运算

#include<bits/stdc++.h>
using namespace std;
using LL = long long;
const LL N = 1e9+7; 
template<int kcz>
struct ModInt {
#define T (*this)
    int x;
    ModInt() : x(0) {}
    ModInt(int y) : x(y >= 0 ? y : y + kcz) {}

    ModInt(LL y) : x(y >= 0 ? y % kcz : (kcz - (-y) % kcz) % kcz) {}

    inline int inc(const int &v) {
        return v >= kcz ? v - kcz : v;
    }

    inline int dec(const int &v) {
        return v < 0 ? v + kcz : v;
    }

    inline ModInt &operator+=(const ModInt &p) {
        x = inc(x + p.x);
        return T;
    }

    inline ModInt &operator-=(const ModInt &p) {
        x = dec(x - p.x);
        return T;
    }

    inline ModInt &operator*=(const ModInt &p) {
        x = (int) ((LL) x * p.x % kcz);
        return T;
    }

    inline ModInt inverse() const {
        int a = x, b = kcz, u = 1, v = 0, t;
        while (b > 0)t = a / b, std::swap(a -= t * b, b), std::swap(u -= t * v, v);
        return u;
    }

    inline ModInt &operator/=(const ModInt &p) {
        T *= p.inverse();
        return T;
    }

    inline ModInt operator-() const {
        return -x;
    }

    inline friend ModInt operator+(const ModInt &lhs, const ModInt &rhs) {
        return ModInt(lhs) += rhs;
    }

    inline friend ModInt operator-(const ModInt &lhs, const ModInt &rhs) {
        return ModInt(lhs) -= rhs;
    }

    inline friend ModInt operator*(const ModInt &lhs, const ModInt &rhs) {
        return ModInt(lhs) *= rhs;
    }

    inline friend ModInt operator/(const ModInt &lhs, const ModInt &rhs) {
        return ModInt(lhs) /= rhs;
    }

    inline bool operator==(const ModInt &p) const {
        return x == p.x;
    }

    inline bool operator!=(const ModInt &p) const {
        return x != p.x;
    }

    inline ModInt qpow(LL n) const {
        ModInt ret(1), mul(x);
        while (n > 0) {
            if (n & 1)ret *= mul;
            mul *= mul, n >>= 1;
        }
        return ret;
    }

    inline friend std::ostream &operator<<(std::ostream &os, const ModInt &p) {
        return os << p.x;
    }

    inline friend std::istream &operator>>(std::istream &is, ModInt &a) {
        LL t;
        is >> t, a = ModInt<kcz>(t);
        return is;
    }

    static int get_mod() {
        return kcz;
    }

    inline bool operator<(const ModInt &A) const {
        return x > A.x;
    }

    inline bool operator>(const ModInt &A) const {
        return x < A.x;
    }
#undef T
};
using Z=ModInt<N>;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int n;cin>>n;
	if(n>8192){
		cout<<"0\n";return 0;
	}
	vector<int> a(n),sum_xor(n+1,0);
	for(auto &x:a)cin>>x;
	/*
		为什么使用前缀异或和？ 
		快速计算任意区间的异或结果
		有了前缀异或和，如果要计算区间 [l, r] 的异或结果
		只需要通过 sum_xor[r+1] ^ sum_xor[l] 即可得到结果
		因为在l之前的数据包都是一样的，异或结果都是0 
	*/
	Z ans = 1;
	for(int i=1;i<=n;i++)sum_xor[i]=sum_xor[i-1]^a[i-1];
	for(int i=1;i<=n;i++){
		for(int j=i;j<=n;j++){
			ans*=sum_xor[i-1]^sum_xor[j];
		}
	} 
	cout<<ans;
 	return 0;
}
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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135

2、异或森林

#include<bits/stdc++.h>
using namespace std;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int n;cin>>n;
	vector<int> a(n),sum_xor(n+1,0);
	for(auto &x:a)cin>>x;
	for(int i=1;i<=n;i++)sum_xor[i]=sum_xor[i-1]^a[i-1];
	/*
		是需要咱们找到连续子数组的数量
		n * (n + 1) / 2 表示长度为1的子数组有 n 个
		长度为2的子数组有 n-1 个，以此类推
		最终得到总共 n * (n + 1) / 2 个子数组
		所以，
		n(n+1)/2 = 连续子数组个数 
	*/
    int ans = n * (n + 1) / 2;
    // 记录每个前缀异或和的次数 
    vector<int> cnt(4 * n + 1);
    cnt[0] = 1;
    /*
    	n  x|n  n/x|n 
		if x=n/x，那么说明这个n的因数就是奇数个了，因为这两个数一样
		所以·判断条件就是 x^2=n
		因为 奇数 个好判断，所以我们列举出来所有可能的数量就是ans
		让 ans 减去奇数个的就行了 
	*/ 
    for (int r = 1; r <= n; r++) {
        for (int i = 0; i * i <= 2 * n; i++) {
            ans -= cnt[sum_xor[r] ^ (i * i)];
        }
        cnt[sum_xor[r]]++;
    }
    cout << ans << '\n';
 	return 0;
}
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

3、位移

#include<bits/stdc++.h>
using namespace std;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int n;cin>>n;
	while(n--){
		unsigned int a,b;cin>>a>>b;
		while(!(a&1))a>>1;
		while(!(b&1))b>>1;
		if(a<b){
			cout<<"No\n";return 0;
		} 
		// 因为输入的是10进制，所以我们要转化这两个数的二进制状态
		vector<int> A,B;
		while(a>0){
			A.push_back(a&1);a=>>1;
		}
		while(b>0){
			B.push_back(b&1);b=>>1;
		}  
		//判断 b 是否在 a 里面
		int n = (int) A.size(), m = (int) B.size();
		// 字符串匹配 
    	for (int i = 0; i + m - 1 < n; i++) {
        	int fl = 0;
        	for (int j = 0; j < m; j++) {
        		// 对于 A 来讲 肯定是 每次移动，B 从头开始的 
            	if (A[i + j] != B[j]) {
                	fl = 1;
                	break;
                }
            }
        }
        if (!fl) {
            cout << "Yes\n";
            return 0;
        }
    	cout << "No\n";
	} 
 	return 0;
}
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

4、笨笨的机器人

#include<bits/stdc++.h>
using namespace std;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
    int n;cin>>n;
	vector<int> a(n);
	for(auto &x:a)cin>>x; 
    int cnt = 0;
    // 枚举集合，此时 S 的每一位表示第 i 个数是加还是减
	// 为了生成长度为 n 的二进制数的所有可能情况
	// 通过这种方法来穷举所有的子集合
    for (int S = 0; S < 1 << n; S++) {
        int p = 0;
        // 求第 i 位是加还是减
        for (int i = 0; i < n; i++) {
            // S >> i & 1 的意思是先做 S >> i，再 & 1，含义是 S 的第 i 位是不是 1
            // S >> i 等价于 S / 2 ^ i 下取整，意味着去除了最后的 i 位，此时个位数 (二进制) 是原数第 i 位
            // x & 1 等价于与 1 取 and，也就是只有 x 的个位与 1 做了 and，即 x 的个位数是不是 1
            if (S >> i & 1)p += a[i];
            else p -= a[i];
        }
        if (p % 7 == 0)cnt++;
    }
    double ans = (double)cnt/(1<<n);
    ans = round(ans * 1e4) / 1e4;
    cout<<fixed<<setprecision(4)<<ans;
 	return 0;
}
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

5、博弈论