题解：P16233 [蓝桥杯 2026 省 B] 双碳战略

CDSuperDuo · 2026-04-13 23:05:52 · 题解

前言

五年级蒟蒻的大号被封，心态调整后的第一次写题解，也是第一次用小号写题解。

这是一道再简单不过的题了 ~~（细节：B 组的填空题居然比 A 组的难度高一点）~~。

题目大意

有 2026 盏路灯，开始时全都是亮的（状态为 1）。

操作规则如下：

奇数次操作（第 1,3,5,\dots 次）：选定一盏路灯 i，翻转它及其右侧（后方）所有路灯的状态。
偶数次操作（第 2,4,6,\dots 次）：选定一盏路灯 i，翻转它及其左侧（前方）所有路灯的状态。

其中所有 2^{2026} 种不同的明暗状态都可以通过若干次操作到达。

对于每种状态，定义它的“最少操作次数”为从初始全亮状态到达该状态所需的最少指令数（初始状态的最少操作次数为 0）。

题目要求我们计算出所有 2^{2026} 种状态的最少操作次数之和，并对 998244353 取模。

解题思路

我们可以发现以下性质：

奇数次操作会影响后缀 [i,n]。
偶数次操作会影响前缀 [1,i]。

操作序列与最终状态一一对应。

通过分析（或者也可以造小数据手动模拟）可以得到：对于 n 盏灯，所有状态的最少操作次数之和为 n \times 2^{n-1}。

具体推导如下：

这里假设 f(n) 表示 n 盏灯时所有状态的最少操作次数之和。

考虑第 n 盏灯最后的状态：

如果是亮的：则它被翻转了偶数次。此时前 n-1 盏灯可以取任何状态，最少操作次数等于前 n-1 盏灯的最少操作次数。共 2^{n-1} 种状态，贡献为 f(n-1)。
如果是暗的：则它被翻转了奇数次。此时前 n-1 盏灯也可以取任何状态，但是我们需要在对应状态的基础上额外加上 1 次操作（以 n 为起点），因为以 n 为起点的操作只影响第 n 盏灯（不影响前面），所以在前 n-1 盏灯的最优解后面追加一次以 n 为起点的操作，就得到第 n 盏为暗的最优解，且步数恰好 +1。共 2^{n-1} 种状态，贡献为 f(n-1) + 2^{n-1}。

因此：

f(n) = 2 \times f(n-1) + 2^{n-1}

又因为 f(1) = 1，递推得：

f(n) = n \times 2^{n-1}

所以最终答案就是

2026 \times 2^{2025} \bmod 998244353

怎么得出结果呢？~~你可以尝试使用计算器，这样的话你就会被判为作弊者啦~~。因此我们可以使用快速幂来解决。

AC Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MOD=998244353;
int ksm(int a,int b,int mod)
{
    int res=1;
    while(b)
    {
        if(b&1) res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}
signed main()
{
    int n=2026;
    int ans=n*ksm(2,n-1,MOD)%MOD;
    cout<<ans;
    return 0;
}

十年 OI 一场空，不开 long long 见祖宗。