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

初始状态下这 2026 盏路灯均处于高能耗的“全亮模式”。为了评估系统在极端工况下的响应能力该局的主控系统需要针对理论上存在的所有开关组合进行全状态遍历推演。只是受限于底层硬件的物理特性主控系统必须严格按照“双向交替”的规则执行操作第奇数次指令第 1,3,5… 次系统需选定一盏路灯 1≤≤2026将该路灯及其右侧后方所有路灯的开关状态进行翻转亮变暗暗变亮。第偶数次指令第 2,4,6… 次系统需选定一盏路灯 将该路灯及其左侧前方所有路灯的开关状态进行翻转。对于 2026 盏路灯共存在 22026 种不同的明暗状态组合每一种状态都必定能被抵达。针对每一种特定的状态都存在一个从初始“全亮”状态到达该状态所需的最少指令操作次数无论有多少种不同的操作序列可以到达该状态仅以步数最少的为准。注意初始的“全亮”状态也包含在这 22026 种组合中且到达该状态的最少操作次数记为 0 次。现在请你计算出这全部 22026 种状态对应的最少操作次数的累加总和。由于总和可能很大请将结果对 998244353 取模后输出。输入格式无输出格式这是一道结果填空题你只需要算出结果后提交即可。本题的结果为一个整数在提交答案时只填写这个整数填写多余的内容将无法得分。输入输出样例 #1输入 #1输出 #1题目链接解题思路因为求最小操作次数等价于求最短路径所以小数据可以用bfs再根据小数据画出图像为“j”型增长那么一定与幂函数有关再观察得每个答案都能被n整除且除完之后特别 “整”、特别 “好看”最后总结得出n*2^(n-1) 由于是2的次幂所以其实可以不用快速幂用左移即可代码实现//n*2^(n-1)//根据小数据画出图像为“j”型增长那么一定与幂函数有关//再观察得每个答案都能被n整除且除完之后特别 “整”、特别 “好看”/*#includebits/stdc.husing namespace std;using lllong long;const int p998244353;ll qmi(ll a,ll b){ll res1;while(b){if(b1)resres*a%p;aa*a%p,b1;}return res%p;}int main(){ll n2026;ll ansn*qmi(2,n-1)%p;coutans\n;return 0;}*///状态空间bfs搞定小数据再用数学归纳法推出结论#include bits/stdc.husing namespace std;const int mod998244353;queuestringq;unordered_mapstring,intdis;int n;//翻转区间[l,r]string flip(string s, int l, int r) {for (int il;ir;i) {s[i]s[i]1?0:1;}return s;}void bfs(string st){dis[st]0;q.push(st);while(q.size()){auto tq.front();q.pop();int stepdis[t]; //当前是第几步//当前偶数下一步奇数次操作翻转i~n-1if(step%20){for(int i0;in;i){string ntflip(t,i,n-1);//dis[nt] 会自动插入不存在的键-破坏 BFS//dis.count(nt) 只查询不插入-安全if(!dis.count(nt)){dis[nt]dis[t]1;q.push(nt);}}}else { //当前奇数下一步偶数次操作翻转0~ifor(int i0;in;i){string ntflip(t,0,i);if(!dis.count(nt)){dis[nt]dis[t]1;q.push(nt);}}}}}int main(){cinn;string st;for(int i0;in;i)st1; //初始全亮bfs(st);long long ans0;for (auto t:dis){int dt.second;ans(ansd)%mod;}coutans\n;return 0;}