A.均衡数


这个就是观察加猜想，我真的哭了

首先取log算一下发现2026202620262026 二进制占51位

但是1和0只能相等，所以要找的位数是偶数

所以x是52位

然后1放首位，其余1放末尾从最小开始，因为其他的数字都会比这个数字大而且x是52位，本身就比N大，所以这个数值就是答案

写一个循环就可，二进制再转换成十进制

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
#include<iostream>

using namespace std;

  

using ll=long long;

  

ll mul(int n){

    if(n==0) return 1;

    if(n==1) return 2;

    else return 2*mul(n-1);

}

  

int main(){

    int a[52];

    a[0]=1;

    for(int i=51;i>=27;i--){

        a[i]=1;

    }

    for(int i=1;i<27;i++){

        a[i]=0;

    }

  

    ll ans=0;

    for(int i=0;i<52;i++){

        if(a[i]==1){

            int n=51-i;

            ans+=mul(n);

        }

    }

  

    cout<<ans<<endl;

    return 0;

}

这个没啥好说的也没有技术含量，但是如果想要偷鸡 投机的话，可以用位运算
这里是大整数，不用pow，因为其返回的是double,数值非常大时会损失精度

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
#include<iostream>

#include<cmath>

using namespace std;

  

typedef long long ll;

  

int  main(){

    //1排在第一位和最后几位，其他是0

    ll ans=(1LL<<51);

    for(int i=0;i<25;i++){

        ans+=(1LL<<i);

    }

    cout<<ans<<endl;

    return 0;

}

为什么要写 1LL 而不是 1？

  • 默认类型问题：在 C++ 中，普通的数字字面量 1 默认是 int 类型（通常只有 32 位）。

  • 溢出风险：一个 32 位的 int 最大只能表示到 2^31 -1

    • 如果你写 1 << 51，编译器会尝试在一个 32 位的空间里移动 51 位。这会导致整数溢出，结果通常会变成 0 或者一个奇怪的负数。

  • LL 的作用：LL 告诉编译器：“请把这个 1 当作 long long 类型（64 位）来处理”。

    • 1LL << 51 能够确保运算是在 64 位的空间内进行的

#位运算特辑
它直接对计算机底层的二进制位进行操作，速度极快。下列是copy下来的介绍

1. 基础运算符速查

  • & (按位与)：全 1 则 1（常用于判断奇偶、取位）。
  • | (按位或)：有 1 则 1（常用于置位）。
  • ^ (按位异或)：不同为 1，相同为 0（常用于找不同、翻转状态）。
  • ~ (按位取反)：0 变 1，1 变 0。
  • >> (右移)：n >> i 相当于 $n / 2^i$。左移就是倒过来

2. 高频实用“神操作”

(1) 判断奇偶

1
2
3
4
if (n & 1) // 等价于 n % 2 != 0
    cout << "奇数";
else
    cout << "偶数";

(2) 取出第 $i$ 位的值（从 0 开始计数）

如果你想知道数字 $n$ 的二进制第 $i$ 位是 0 还是 1：

1
int bit = (n >> i) & 1;

(3) 常用位操作三板斧

  • 将第 $i$ 位置为 1：n | (1LL << i)
  • 将第 $i$ 位置为 0：n & ~(1LL << i)，就和变为1是一样的，只不过取了个反
  • 将第 $i$ 位取反（0变1, 1变0）：n ^ (1LL << i)，是异或吼吼吼

哎真的很巧妙。

(4) 快速判断一个数是不是 2 的幂次

如果一个数 $n$ 是 2 的幂（如 2, 4, 8, 16…），它的二进制只有一个 1。

1
2
if (n > 0 && (n & (n - 1)) == 0) 
    // 是 2 的幂

(5) Lowbit 运算（树状数组核心）

取出 $n$ 的二进制中最低位的那个 1 及其后面的 0。

1
2
int lowbit = n & -n; 
// 比如 n = 6 (110)，lowbit = 2 (010)

3. 两个最重要的“坑”

第一：优先级问题（非常重要！）

位运算符的优先级通常比加减法低。

  • 错误写法：if (1LL << i + 1)
  • 编译器实际执行的是：1LL << (i + 1)
  • 保险做法：永远记得给位运算加括号！
    • 比如：if ((n >> i) & 1) 而不是 if (n >> i & 1)。

第二：__builtin 系列函数（黑科技）

C++ 编译器（GCC）内置了一些非常强大的位运算函数，蓝桥杯是可以用的：

  • __builtin_popcount(n)：返回 $n$ 的二进制中 1 的个数。（这题如果用这个函数暴力枚举，可能直接就出答案了，，。。）
  • __builtin_popcountll(n)：针对 long long 版本的 1 的个数。
  • __builtin_clz(n)：返回前导 0 的个数。
    咋说呢，这个我感觉没必要记忆。

4. 针对本题的“暴力”解法参考

如果当时想不出构造法，可以用位运算暴力寻找：

1
2
3
4
5
6
7
8
9
using ll = long long;
ll N = 2026202620262026LL;

// 暴力往上搜（填空题电脑跑几十秒没关系）
for (ll x = N; ; x++) {
    // 假设用某个方法算 x 的位数是 len
    // 如果 __builtin_popcountll(x) * 2 == len，说明是均衡数
    // 这种方法在比赛中非常稳
}

我的天。泪洒现场我也不知道我当时在干嘛。

B.量子2048

我以为是bfs或者是其他的，结果题解说是组合数学于异或线性方程组问题
先抛出来结论，只要确定了第一行和第一列的所有数值（2*n-1），全局就确定了

思考过程：

把xij=0看成L状态，把1看成Q状态


ai对应第一列信息，bj对应第一行的信息

好的。是时候开始大惑不解追根溯源了，怎么就推出来最后一个公式的，很诡异而且出现的莫名其妙，哎呀这个推导过程看的我真不想活了唉

公式的由来

我们知道准则三说


那再定义一个辅助变量，表示第i行中相邻两列的差异，那上式可以写成

这意味着：下一行的相邻列差异，永远是上一行的差异取反
可以递推出第i行与第一行的关系

这里的 (i−1)要么是 0 要么是 1，代表异或了 i−1次 1


化简


好的，就得到了那坨公式

然后咋算

1. “自由度” (Degrees of Freedom)？

想象你有 3 个开关：$a, b, c$。每个开关可以开（1）或关（0）。

  • 如果你没有任何约束，你有 $2^3 = 8$ 种方案。
  • 现在我给你 1 个方程（约束）：$a \oplus b \oplus c = 1$。

在这个方程里，你可以随便选 $a$ 和 $b$ 的状态（比如 $a=1, b=0$），但一旦你选好了，$c$ 的状态就被锁死了（必须让方程成立，这里 $c$ 只能是 0）。
也就是说，1 个独立的方程，会**“杀掉”1 个自由选择的位**。

结论：方案数 = $2^{\text{总变量数} - \text{独立方程数}}$

2. 我们一共有多少个变量？

根据公式 $x_{i,j} = a_i \oplus b_j \oplus (i-1)(j-1)$，整个阵列取决于：

  • $a_1, a_2, \dots, a_{2048}$ （第一列的 $n$ 个变量）
  • $b_1, b_2, \dots, b_{2048}$ （第一行的 $n$ 个变量）

这里一共有 $2n$ 个变量。
但是注意！ 公式里只有 $a_i \oplus b_j$。如果你把所有的 $a_i$ 都取反，同时把所有的 $b_j$ 也都取反，$a_i \oplus b_j$ 的结果是不变的。
这意味着 $a_1$ 和 $b_1$ 之间存在冗余。我们可以固定 $b_1 = a_1$（或者干脆认为 $a_1$ 和 $b_1$ 是同一个变量），这样初始的有效变量总数就是：
$$2n - 1$$

3. 我们一共有多少个约束方程？

刚才推导过，行约束和列约束在代入公式后，发生了奇妙的简化：

  • 行约束（准则 1）：虽然有 $n$ 行，但因为 $n=2048$ 是偶数，所有的行约束最后都变成了同一个方程：
    $$\sum b_j = 1 \pmod 2$$
    （这算 1 个独立约束）

  • 列约束（准则 2）：同理，所有的列约束最后也都变成了同一个方程：
    $$\sum a_i = 1 \pmod 2$$
    （这又算 1 个独立约束）

  • 局部约束（准则 3）：这个约束已经被我们写成 $x_{i,j} = \dots$ 的形式了，它并不产生新的方程，而是已经帮我们消掉了除了第一行第一列之外的所有变量。

所以，我们现在手里有：

  • 总变量：$2n - 1$ 个
  • 独立方程：$2$ 个

4. 最终方案数的计算

自由变量（可以随便选的位数） = $(2n - 1) - 2 = 2n - 3$。

把 $n = 2048$ 代入：
$$2n - 3 = 2 \times 2048 - 3 = 4096 - 3 = 4093$$

因为每个自由变量都有 0 和 1 两种选法，所以总方案数就是：
$$\mathbf{2^{4093}}$$

最后用快速幂算一下即可，finish!!!