要解决这个问题，我们需要找到一种高效的方法来模拟灯泡状态的变化，尤其是当时间步长 m 非常大（可达 \(10^9\)）时，直接逐时刻模拟是不可行的。通过分析状态变化的规律，我们可以利用 倍增法（类似快速幂的思想）来快速计算最终状态。

方法思路

1. 状态转换与规律发现：

   • 将灯泡状态 b（亮）记为 1，d（不亮）记为 0。
   • 状态转移规则：时刻 t 的状态 s[t][i] 由时刻 t-1 的状态决定，即 s[t][i] = s[t-1][i] XOR s[t-1][left(i)]，其中 left(i) 是第 i 个灯泡左边的灯泡（环形排列）。
   • 通过数学归纳法可证明：当时间步长为 (2^k) 时，状态转移可简化为 s[t][i] = s_prev[i] XOR s_prev[(i - 2^k) mod n]，其中 s_prev 是 (2^k) 步前的状态。

2. 倍增法应用：

   • 将 m 分解为二进制，例如 \(m = 2^{k_1} + 2^{k_2} + \dots\)。
   • 依次应用每个 \(2^k\) 步的状态转移，最终得到时刻 m 的状态。

解决代码

#include <iostream>
#include <vector>
#include <string>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    long long m;
    cin >> n >> m;
    string s;
    cin >> s;

    vector<int> curr(n);
    for (int i = 0; i < n; ++i) {
        curr[i] = (s[i] == 'b') ? 1 : 0;
    }

    for (int k = 0; k <= 30; ++k) {
        if (m & (1LL << k)) {
            long long t = 1LL << k;
            vector<int> next(n);
            for (int i = 0; i < n; ++i) {
                long long pos = (long long)i - t;
                pos = (pos % n + n) % n;
                next[i] = curr[i] ^ curr[(int)pos];
            }
            curr = move(next);
        }
    }

    for (int i = 0; i < n; ++i) {
        cout << (curr[i] ? 'b' : 'd');
    }
    cout << endl;

    return 0;
}

代码解释

1. 输入处理：

   • 读取灯泡数量 n、时刻 m 和初始状态字符串 s。
   • 将初始状态转换为整数数组 curr，1 表示 b，0 表示 d。

2. 倍增法状态转移：

   • 遍历 m 的二进制位，对于每一位 k（对应 \(2^k\) 步），若该位为 1，则应用 \(2^k\) 步的状态转移。
   • 计算新状态 next：next[i] = curr[i] XOR curr[(i - 2^k) mod n]，其中 (i - 2^k) mod n 确保索引在合法范围内。

3. 输出结果：

   • 将最终状态数组 curr 转换回字符并输出，1 输出 b，0 输出 d。

复杂度分析

• 时间复杂度：\(O(30 \times n)\)，其中 30 是 \(2^{30}\) 覆盖 \(10^9\) 的位数，n 是灯泡数量。该复杂度完全满足 \(n \leq 10^5\) 的限制。
• 空间复杂度：\(O(n)\)，使用两个数组存储当前状态和下一个状态，空间效率高。

该方法通过倍增法将时间复杂度从 \(O(m \times n)\) 优化到 \(O(\log m \times n)\)，能够高效处理大规模输入。

模拟稳超时...

...........................

和2^k有关的数学方法

Accepted 有效得分：100 有效耗时：405ms

悲剧了，字符一开始打错了=.=

为什么我的速度这么慢……（好像数组开太大了……）

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 25ms

├ 测试数据 07：答案正确... 9ms

├ 测试数据 08：答案正确... 87ms

├ 测试数据 09：答案正确... 40ms

├ 测试数据 10：答案正确... 56ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：217ms

一次AC

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 25ms

├ 测试数据 07：答案正确... 25ms

├ 测试数据 08：答案正确... 88ms

├ 测试数据 09：答案正确... 88ms

├ 测试数据 10：答案正确... 88ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：314ms

我和4楼的一样：

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 134ms

├ 测试数据 04：运行超时...

├ 测试数据 05：运行超时...

├ 测试数据 06：运行超时...

├ 测试数据 07：运行超时...

├ 测试数据 08：运行超时...

├ 测试数据 09：运行超时...

├ 测试数据 10：运行超时...

反正结论就是：

如果t时刻第p个灯状态为x[p]，则t+2^k时刻第p个灯泡状态为：t时刻第p个灯的状态 xor t时刻p朝左数2^k个灯的状态,即x[p] xor x[(p-2^k-1)mod n+1]。

还有，题目描述有误，实际的数据范围应为：

100%的数据，1≤n≤1000000

这题本质和P1554硬币游戏一样。

第一次格式错误，第二次同样的程序却秒杀，这是为什么

好题啊，没想到

好题目！

为什么我想不到呢。。。郁闷。。。

sdfghsfghjdgh

那个规律很有意思.

注意滚动数组别滚错了- -

AC了.

其实就是找规律,将m分解为2的幂的和(x1,x2,x3,x4..xt),

然后每个时刻j的的每个灯泡状态Ai就是上一个时刻的灯泡状态Bi xor B[(i+xj) mod n].

可以用滚动数组来节省空间.

vikeydr转的那个证明太强了OrzOrz

while m0 do begin p:=c; c:=not c; k:=m and -m; m:=m xor k; for i:=0 to n-1 do f[c,(i+k) mod n]:=f[p,i] xor f[p,(i+k) mod n];end;

Who can give me this key?

i can't ac.

thanks!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

观察杨辉三角可得规律：2^p+1行（即(x+y)^p的展开式系数）只有首尾为奇数，因此题目中只要m=2^p，则可以快速求出，若m2^p，将m分解成2的幂之和后依次求。

( 2007-7-31 18:43:54 )

爽哉

你们大家都把Dennis用来投稿赚钱的文章给贴出来了都