当前位置: 首页 > news >正文

2025牛客暑期多校第4场——G

在这里插入图片描述

考虑一个序列最中间的左括号和右括号,如果这两个交换那么序列是不合法的,由此可以猜测确定操作序列唯一确定的条件。利用一种抽象的前缀和,把左括号看成 111 ,右括号看成 −1-11 ,对于一个左括号,如果和一个右括号中间的有一个前缀和是 <2<2<2 的,那么操作序列就可以唯一确定,每次枚举左括号位置,计算合法方案数求和即可.

为什么每个左括号都可以计算答案,因为一个合法序列的左括号都有一个右括号与之匹配

#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
using i128 = __int128;constexpr int mod = 998244353;
constexpr int maxn = 1e6+10;
int pre[maxn];
i64 qp(i64 a,i64 b){i64 ans = 1;while(b){if(b&1) ans = ans*a%mod;b>>=1;a = a*a%mod;}return ans;
}
void solve(){string s;cin>>s;for(int i = 0;i<s.size();++i){pre[i+1] = pre[i]+(s[i]=='('?1:-1); }int n = s.size();i64 ans = qp(2,n>>1);int cntl=n/2, cntr = 1,cntrr=1;for(int i = s.size()-2;i>=0;--i){if(pre[i+1]<2){cntr=cntrr;}if(s[i]=='(') cntl--;else cntrr++;if(s[i]=='('){(ans+=qp(2,cntl+cntr))%=mod;}}cout<<ans*qp(qp(2,n),mod-2)%mod<<"\n";
}signed main(){ios::sync_with_stdio(0);cin.tie(0);int t=1;//cin>>t;while(t--) solve();return 0;
}
http://www.lryc.cn/news/600242.html

相关文章:

  • MCP协议深度解析:客户端-服务器架构的技术创新
  • CMakeLists.txt 怎么写
  • 电脑开机后网络连接慢?
  • @PathVariable与@RequestParam的区别
  • 【洛谷】单向链表、队列安排、约瑟夫问题(list相关算法题)
  • 刷题日记0725
  • 二开----02
  • 【前端工程化】前端项目开发过程中如何做好通知管理?
  • Model Control Protocol 三层架构设计,三种传输方式,完成MCP项目构建实现工具调试,多维度评价指标检测多工具多资源调用的鲁棒性和稳健性
  • 从零本地部署使用Qwen3-coder进行编程
  • Web开发传参的四种常见方式介绍
  • 太极生两仪,两仪生四象,四象生八卦
  • 智慧电视:开启养老新时代
  • 【图像理解进阶】如何对图像中的小区域进行细粒度的语义分割?
  • [2025CVPR-图象分类方向]CATANet:用于轻量级图像超分辨率的高效内容感知标记聚合
  • Python day24
  • day 35打卡
  • DNS 协议
  • OSI 七层模型和五层模型
  • Effective C++ 条款02:尽量以 const, enum, inline 替换 #define
  • HTTP 请求方法有哪些?
  • 浅析PCIe 6.0 ATS地址转换功能
  • LP-MSPM0G3507学习--11ADC之二双通道高速DMA采样
  • Sweet Home 3D:一款免费的室内装修辅助设计软件
  • cocos creator 3.8.6 websocke的一直报错WebSocket is not a constructor
  • 力扣面试150题--寻找旋转排序数组中的最小值
  • 关于数据库表id自增问题
  • 第5章 Excel公式与函数应用指南(1):公式和函数基础
  • deepseek本地部署,轻松实现编程自由
  • 【实操记录】docker hello world