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

D. Anton and School - 2

范德蒙德恒等式

\sum_{i=0}^{n}\binom{n}{i}*\binom{m}{x-i} = \binom{n+m}{x}

考虑统计每一个右括号位置的贡献,也就是每个右括号作为右边起点的贡献

\sum_{i=1}^{r}\binom{l}{i}\binom{r-1}{i-1}= \sum_{i=1}^{r}\binom{l}{i}\binom{r-1}{r-i} = \binom{l+r-1}{r}

其中i=0的时候,r-1<r-0,故i=0时贡献为0,直接套用恒等式不会有影响

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
# define mod 1000000007
ll fac[1000000+10],inv[1000000+10];
ll qp(ll base, ll pow)
{ll ans=1;while(pow){if(pow&1)ans=ans*base%mod;pow>>=1;base=base*base%mod;}return ans;
}
void init()
{fac[0]=1;for(int i=1;i<=1000000;i++){fac[i]=fac[i-1]*(ll)i%mod;}inv[1000000]=qp(fac[1000000],mod-2);for(int i=1000000-1;i>=0;i--){inv[i]=(ll)(i+1)*inv[i+1]%mod;}
}
ll getc(int x,int y)
{if(x<y)return 0;return fac[x]*inv[y]%mod*inv[x-y]%mod;
}
int l[200000+10],r[200000+10];
int main()
{init();string s;cin>>s;s=" "+s;for(int i=1;i<s.length();i++){l[i]+=l[i-1];l[i]+=(s[i]=='(');}for(int i=s.length()-1;i>=1;i--){r[i]+=r[i+1];r[i]+=(s[i]==')');}ll ans=0;for(int i=2;i<s.length();i++){if(s[i]==')'){ans+=getc(r[i]+l[i]-1,r[i]);ans%=mod;}}cout<<ans;return 0;
}

 

相关文章:

D. Anton and School - 2

范德蒙德恒等式 考虑统计每一个右括号位置的贡献&#xff0c;也就是每个右括号作为右边起点的贡献 其中i0的时候&#xff0c;r-1<r-0,故i0时贡献为0&#xff0c;直接套用恒等式不会有影响 #include <bits/stdc.h> using namespace std; typedef long long int ll; # d…...

xcode把包打到高版本的iPhone里

打开xcode CTRLb build工程&#xff0c;build成功 把手机连到mac&#xff0c;在xcode选项卡里面的window里面选中device and simulator 打开对应的手机的页面 然后在工程目录下build成功过后有一个product的文件夹里面&#xff0c;直接把app拖到对应的手机的窗口就可以不用…...

PMP项目管理考试小结

一、初步了解 每年有多次考试的机会&#xff0c;大概每三-四个月有一次考试机会&#xff0c;我下面分享的是我考试&#xff1a; 考试时间&#xff1a;8月19日 上午9:00-12:50 考试地点&#xff1a;北京市丰台区首都经济贸易大学&#xff08;城市不一样考点不一样&#xff09; …...

【NAS群晖drive异地访问】使用cpolar远程访问内网Synology Drive「内网穿透」

文章目录 前言1.群晖Synology Drive套件的安装1.1 安装Synology Drive套件1.2 设置Synology Drive套件1.3 局域网内电脑测试和使用 2.使用cpolar远程访问内网Synology Drive2.1 Cpolar云端设置2.2 Cpolar本地设置2.3 测试和使用 3. 结语 前言 群晖作为专业的数据存储中心&…...

【傅里叶级数与傅里叶变换】数学推导——2、[Part2:T = 2 π的周期函数的傅里叶级数展开] 及 [Part3:周期为2L的函数展开]

文章内容来自DR_CAN关于傅里叶变换的视频&#xff0c;本篇文章提供了一些基础知识点&#xff0c;比如三角函数常用的导数、三角函数换算公式等。 文章全部链接&#xff1a; 基础知识点 Part1&#xff1a;三角函数系的正交性 Part2&#xff1a;T2π的周期函数的傅里叶级数展开 P…...

【IMX6ULL驱动开发学习】06.DHT11温湿度传感器驱动程序编写与测试

一、DHT11简介 DHT11是一款可测量温度和湿度的传感器。比如市面上一些空气加湿器&#xff0c;会测量空气中湿度&#xff0c;再根据测量结果决定是否继续加湿。 DHT11数字温湿度传感器是一款含有已校准数字信号输出的温湿度复合传感器&#xff0c;具有超小体积、极低功耗的特点…...

sip开发从理论到实践,让你快速入门sip

目录 引言&#xff1a; sip协议是什么&#xff1f; sip的网络结构&#xff08;重点&#xff09; sip的特点 sip使用的url sip协议的应用领域 sip协议基本的消息类型 请求消息 响应消息 sip协议的消息结构&#xff08;这个是重点&#xff09; sip的常见会话流程&#xf…...

十三、Linux中必须知道的几个快捷键!!!

1、强制停止 当某些代码正在运行时&#xff0c;你想让其停止&#xff0c;只需要按下如下快捷键即可&#xff1a; 【CTRL】【C】 示例&#xff1a; 2、退出 Linux系统自带python3解释器&#xff0c;当你进入python3解释器之后&#xff0c;需要退出时&#xff0c;只需要按下&am…...

Django进阶-文件上传

普通文件上传 定义 用户可以通过浏览器将图片等文件上传到网站 场景 用户上传头像 上传流动性的文档【pdf&#xff0c;txt】等 上传规范-后端 1.视图函数中&#xff0c;用request。FILES取文件框的内容 file request.FILES[xxx] 说明&#xff1a; 1.FILES的key对应页面中…...

clickhouse-数据导入导出方案

一、简介 clickhouse有多种数据的导入导出方式&#xff0c;可以灵活使用&#xff0c;下面对这些方式分别做些介绍&#xff0c;导入导出的写法与格式和格式设置有关。 二、导入 1.从s3导入 详情可查看官网&#xff0c;也可以在这里获取数据集 -- 建库建表 CREATE DATABASE …...

[JavaWeb]【一】入门JavaWeb开发总概及HTML、CSS、JavaScript

目录 一 特色 二 收获​编辑 三 什么是web? 四 网站的工作流程 五 web网站的开发模式​编辑 六 web开发课程学习安排 七、初始web前端 八 HTML、CSS 8.1 什么是HTNL\CSS(w3cschool) 8.2 HTML快速入门 8.3 VS Code开发工具 8.3.1 插件 8.3.2 主题&#xff08;改变颜色&…...

Python自动化小技巧18——自动化资产月报(word设置字体表格样式,查找替换文字)

案例背景 每月都要写各种月报&#xff0c;经营管理月报&#xff0c;资产月报.....这些报告文字目标都是高度相似的&#xff0c;只是需要替换为每个月的实际数据就行&#xff0c;如下&#xff1a; (打码是怕信息泄露.....) 可以看到&#xff0c;这个报告的都是高度模板化&…...

FFmpeg5.0源码阅读——VideoToobox硬件解码

摘要&#xff1a;本文描述了FFmpeg中videotoobox解码器如何进行解码工作&#xff0c;如何将一个编码的码流解码为最终的裸流。   关键字&#xff1a;videotoobox,decoder,ffmpeg   VideoToolbox 是一个低级框架&#xff0c;提供对硬件编码器和解码器的直接访问。 它提供视频…...

IDEA 中Tomcat源码环境搭建

一、从仓库中拉取源代码 配置仓库地址、项目目录&#xff1b;点击Clone按钮&#xff0c;从仓库中拉取代码 Tomcat源码对应的github地址&#xff1a; https://github.com/apache/tomcat.git 二、安装Ant插件 打开 File -> Setting -> Plugins 三、添加Build文件 &…...

MATLAB | 七夕节用MATLAB画个玫瑰花束叭

Hey又是一年七夕节要到了&#xff0c;每年一次直男审美MATLAB绘图大赛开始hiahiahia&#xff0c;真的这些代码越写越不知道咋写&#xff0c;又不想每年把之前的代码翻出来再发一遍&#xff0c;于是今年又对我之前写的老代码进行了点优化组合&#xff0c;整了个花球变花束&#…...

嵌入式开发之configure

1 前述 在Linux的应用或者驱动开发过程中&#xff0c;编写makefile是无法避免的问题&#xff0c;但是由于makefile的各种规则&#xff0c;或显式&#xff0c;或隐式&#xff0c;非常多&#xff0c;不经常写的话&#xff0c;很难写出一个可用的makefile文件。为了“偷懒”&…...

深入浅出Pytorch函数——torch.nn.Module

分类目录&#xff1a;《深入浅出Pytorch函数》总目录 Pytorch中所有网络的基类&#xff0c;我们的模型也应该继承这个类。Modules也可以包含其它Modules,允许使用树结构嵌入他们&#xff0c;我们还可以将子模块赋值给模型属性。 语法 torch.nn.Module(*args, **kwargs)方法 …...

【100天精通python】Day38:GUI界面编程_PyQt 从入门到实战(中)_数据库操作与多线程编程

目录 专栏导读 4 数据库操作 4.1 连接数据库 4.2 执行 SQL 查询和更新&#xff1a; 4.3 使用模型和视图显示数据 5 多线程编程 5.1 多线程编程的概念和优势 5.2 在 PyQt 中使用多线程 5.3 处理多线程间的同步和通信问题 5.3.1 信号槽机制 5.3.2 线程安全的数据访问 Q…...

STM32--TIM定时器(3)

文章目录 输入捕获简介频率测量输入捕获通道输入捕获基本结构PWMI的基本结构输入捕获模式测量PWM频率和占空比代码 编码器接口正交编码器工作模式接口基本结构TIM编码接口器测速代码&#xff1a; 输入捕获简介 输入捕获IC(Input Capture)&#xff0c;是处理器捕获外部输入信号…...

爬虫框架- feapder + 爬虫管理系统 - feaplat 的学习简记

文章目录 feapder 的使用feaplat 爬虫管理系统部署 feapder 的使用 feapder是一款上手简单&#xff0c;功能强大的Python爬虫框架 feapder 官方文档 文档写的很详细&#xff0c;可以直接上手。 基本命令&#xff1a; 创建爬虫项目 feapder create -p first-project创建爬虫 …...

Docker 离线安装指南

参考文章 1、确认操作系统类型及内核版本 Docker依赖于Linux内核的一些特性&#xff0c;不同版本的Docker对内核版本有不同要求。例如&#xff0c;Docker 17.06及之后的版本通常需要Linux内核3.10及以上版本&#xff0c;Docker17.09及更高版本对应Linux内核4.9.x及更高版本。…...

RocketMQ延迟消息机制

两种延迟消息 RocketMQ中提供了两种延迟消息机制 指定固定的延迟级别 通过在Message中设定一个MessageDelayLevel参数&#xff0c;对应18个预设的延迟级别指定时间点的延迟级别 通过在Message中设定一个DeliverTimeMS指定一个Long类型表示的具体时间点。到了时间点后&#xf…...

QMC5883L的驱动

简介 本篇文章的代码已经上传到了github上面&#xff0c;开源代码 作为一个电子罗盘模块&#xff0c;我们可以通过I2C从中获取偏航角yaw&#xff0c;相对于六轴陀螺仪的yaw&#xff0c;qmc5883l几乎不会零飘并且成本较低。 参考资料 QMC5883L磁场传感器驱动 QMC5883L磁力计…...

解决Ubuntu22.04 VMware失败的问题 ubuntu入门之二十八

现象1 打开VMware失败 Ubuntu升级之后打开VMware上报需要安装vmmon和vmnet&#xff0c;点击确认后如下提示 最终上报fail 解决方法 内核升级导致&#xff0c;需要在新内核下重新下载编译安装 查看版本 $ vmware -v VMware Workstation 17.5.1 build-23298084$ lsb_release…...

企业如何增强终端安全?

在数字化转型加速的今天&#xff0c;企业的业务运行越来越依赖于终端设备。从员工的笔记本电脑、智能手机&#xff0c;到工厂里的物联网设备、智能传感器&#xff0c;这些终端构成了企业与外部世界连接的 “神经末梢”。然而&#xff0c;随着远程办公的常态化和设备接入的爆炸式…...

iOS性能调优实战:借助克魔(KeyMob)与常用工具深度洞察App瓶颈

在日常iOS开发过程中&#xff0c;性能问题往往是最令人头疼的一类Bug。尤其是在App上线前的压测阶段或是处理用户反馈的高发期&#xff0c;开发者往往需要面对卡顿、崩溃、能耗异常、日志混乱等一系列问题。这些问题表面上看似偶发&#xff0c;但背后往往隐藏着系统资源调度不当…...

省略号和可变参数模板

本文主要介绍如何展开可变参数的参数包 1.C语言的va_list展开可变参数 #include <iostream> #include <cstdarg>void printNumbers(int count, ...) {// 声明va_list类型的变量va_list args;// 使用va_start将可变参数写入变量argsva_start(args, count);for (in…...

打手机检测算法AI智能分析网关V4守护公共/工业/医疗等多场景安全应用

一、方案背景​ 在现代生产与生活场景中&#xff0c;如工厂高危作业区、医院手术室、公共场景等&#xff0c;人员违规打手机的行为潜藏着巨大风险。传统依靠人工巡查的监管方式&#xff0c;存在效率低、覆盖面不足、判断主观性强等问题&#xff0c;难以满足对人员打手机行为精…...

华为OD机试-最短木板长度-二分法(A卷,100分)

此题是一个最大化最小值的典型例题&#xff0c; 因为搜索范围是有界的&#xff0c;上界最大木板长度补充的全部木料长度&#xff0c;下界最小木板长度&#xff1b; 即left0,right10^6; 我们可以设置一个候选值x(mid)&#xff0c;将木板的长度全部都补充到x&#xff0c;如果成功…...

【iOS】 Block再学习

iOS Block再学习 文章目录 iOS Block再学习前言Block的三种类型__ NSGlobalBlock____ NSMallocBlock____ NSStackBlock__小结 Block底层分析Block的结构捕获自由变量捕获全局(静态)变量捕获静态变量__block修饰符forwarding指针 Block的copy时机block作为函数返回值将block赋给…...