题目理解

我们有一个长度为 n 的二进制序列（基因型），每天发生如下变异：

• 移除最左边的基因 X₁
• 计算 X₁ ⊕ X₂（异或）
• 把这个结果放到序列最右边

例如：

初始: [X₁, X₂, X₃, ..., Xₙ]
一天后: [X₂, X₃, ..., Xₙ, X₁⊕X₂]

我们需要计算 d 天后的序列，其中 d 可能非常大（最多 10¹⁵）。

关键观察

1. 线性性

变异规则是线性的（只涉及异或运算），这意味着：

• 如果我们知道每个初始基因对最终结果的贡献，可以直接计算
• 可以用矩阵来描述这种线性变换

2. 矩阵表示

定义变换矩阵 T，使得：

新序列 = T × 旧序列

对于题目中的变异规则，矩阵 T 是：

• T[i][i+1] = 1（对于 i = 1 到 n-1），表示基因向右移动一位
• T[n][1] = 1 且 T[n][2] = 1，表示最后一个位置是前两个位置的异或
• 其他位置为 0

3. 多天变异

d 天后的变异就是应用变换矩阵 d 次：

最终序列 = T^d × 初始序列

算法设计

1. 矩阵快速幂

直接模拟 d 天需要 O(nd) 时间，对于 d = 10¹⁵ 不可行。

使用矩阵快速幂：

• 计算 T^d 只需要 O(log d) 次矩阵乘法
• 每次矩阵乘法 O(n³)，但可以用 bitset 优化

2. Bitset 优化

由于矩阵元素只有 0 和 1，可以用 bitset 来：

• 压缩存储空间
• 利用位并行加速矩阵运算

代码详解

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 7e2;
int n, d;
string s;
int v[N + 5], rs[N + 5];

// 定义矩阵结构体，使用bitset存储
struct mat {
    bitset < N + 5 > a[N + 5];
    
    // 矩阵乘法重载（在GF(2)上，即异或运算）
    friend mat operator * (const mat &x, const mat &y) {
        mat res;
        for (int i = 1; i <= n; i++) {
            for (int k = 1; k <= n; k++) {
                if (x.a[i][k]) {
                    res.a[i] ^= y.a[k];  // 异或相当于模2加法
                }
            }
        }
        return res;
    }
};

// 矩阵快速幂
mat qp(mat x, int y) {
    mat res;
    // 初始化单位矩阵
    for (int i = 1; i <= n; i++)
        res.a[i][i] = 1;
    
    while (y) {
        if (y & 1)
            res = res * x;
        x = x * x;
        y >>= 1;
    }
    return res;
}

mat t, res;

signed main() {
    cin >> n >> d >> s;
    s = ' ' + s;
    
    // 读取初始序列
    for (int i = 1; i <= n; i++)
        v[i] = s[i] - '0';
    
    // 构建变换矩阵 T
    for (int i = 1; i < n; i++)
        t.a[i][i + 1] = 1;  // 基因向右移动
    
    t.a[n][1] = 1;  // 最后一个位置包含第一个基因
    t.a[n][2] = 1;  // 最后一个位置包含第二个基因
    
    // 计算 T^d
    res = qp(t, d);
    
    // 计算最终序列：最终序列 = T^d × 初始序列
    for (int i = 1; i <= n; i++) {
        rs[i] = 0;
        for (int k = 1; k <= n; k++)
            if (res.a[i][k])
                rs[i] ^= v[k];
    }
    
    // 输出结果
    for (int i = 1; i <= n; i++)
        cout << rs[i];
    
    return 0;
}

复杂度分析

• 时间复杂度：O(n³ log d / w)
  • 矩阵乘法 O(n³)，但 bitset 优化后约为 O(n³ / w)，其中 w 是机器字长（通常 64）
  • 快速幂需要 O(log d) 次矩阵乘法
• 空间复杂度：O(n²)

学习要点

1. 线性变换思想：将复杂操作转化为矩阵乘法
2. 快速幂技巧：适用于任何满足结合性的操作
3. Bitset 优化：处理 0/1 矩阵的高效方法
4. 模 2 运算：异或的线性代数性质

扩展思考

这种方法可以推广到：

• 其他线性变异规则
• 循环移位加上任意线性组合
• 状态压缩 DP 的优化

这种"将操作表示为矩阵并用快速幂加速"的思路在竞赛中非常常见，是重要的算法技巧。