【智力测试——二分、前缀和、乘法逆元、组合计数】
题目

代码
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int mod = 1e9 + 7;
const int N = 1e5 + 10;
int r[N], c[N], f[2 * N];
int nr[N], nc[N], nn, nm;
int cntr[N], cntc[N];
int n, m, t;void init(int n) {f[0] = f[1] = 1;for (int i = 2; i <= n; i++)f[i] = (ll)f[i - 1] * i % mod;
}ll qmi(ll base, int expo) {ll retv = 1;while (expo) {if (expo & 1)retv = retv * base % mod;base = base * base % mod;expo >>= 1;}return retv;
}void discretize() {int last = -1;for(int i = 1; i <= n; i++) {if(nr[i] > last) ++nn, cntr[nn]++, last = nr[i];else cntr[nn]++;}last = -1;for(int i = 1; i <= m; i++) {if(nc[i] > last) ++nm, cntc[nm]++, last = nc[i];else cntc[nm]++;}cntr[0] = 1;for(int i = 1; i <= nn; i++)cntr[i] = (ll)cntr[i] * cntr[i-1] % mod;cntc[0] = 1;for(int i = 1; i <= nm; i++)cntc[i] = (ll)cntc[i] * cntc[i-1] % mod;nn = unique(nr+1, nr+n+1) - nr - 1;nm = unique(nc+1, nc+m+1) - nc - 1;
}int main() {ios::sync_with_stdio(0);cin.tie(0);init(2e5);cin >> n >> m >> t;for (int i = 1; i <= n; i++)cin >> r[i], nr[i] = r[i];for (int i = 1; i <= m; i++)cin >> c[i], nc[i] = c[i];sort(nr + 1, nr + n + 1);sort(nc + 1, nc + m + 1);discretize();while (t--) {int sr, sc, tr, tc;cin >> sr >> sc >> tr >> tc;if ((r[tr] <= r[sr] && tr != sr) || (c[tc] <= c[sc] && tc != sc)) {cout << 0 << '\n';continue;}int srp = lower_bound(nr + 1, nr + nn + 1, r[sr]) - nr;int trp = lower_bound(nr + 1, nr + nn + 1, r[tr]) - nr;int scp = lower_bound(nc + 1, nc + nm + 1, c[sc]) - nc;int tcp = lower_bound(nc + 1, nc + nm + 1, c[tc]) - nc;int drp = trp - srp;int dcp = tcp - scp;int ans = (ll)f[drp + dcp] * qmi(f[drp], mod - 2) % mod * qmi(f[dcp], mod - 2) % mod;if(drp) ans = (ll)ans * cntr[trp-1] % mod * qmi(cntr[srp], mod-2) % mod;if(dcp) ans = (ll)ans * cntc[tcp-1] % mod * qmi(cntc[scp], mod-2) % mod;cout << ans << '\n';}
}
相关文章:
【智力测试——二分、前缀和、乘法逆元、组合计数】
题目 代码 #include <bits/stdc.h> using namespace std; using ll long long; const int mod 1e9 7; const int N 1e5 10; int r[N], c[N], f[2 * N]; int nr[N], nc[N], nn, nm; int cntr[N], cntc[N]; int n, m, t;void init(int n) {f[0] f[1] 1;for (int i …...
Spring Security(maven项目) 3.0.2.9版本 --- 改
前言: 通过实践而发现真理,又通过实践而证实真理和发展真理。从感性认识而能动地发展到理性认识,又从理性认识而能动地指导革命实践,改造主观世界和客观世界。实践、认识、再实践、再认识,这种形式,循环往…...
并发编程中的常见问题
1 竞态条件 (Race Condition) 定义:竞态条件是指多个线程在访问共享资源时,由于执行顺序的不同导致结果不确定的情况。 示例: public class Counter {private int count = 0;public void increment() {count++;}public int getCount() {return count;} }在多线程环境下,…...
二维前缀和:高效求解矩阵区域和问题
在处理二维矩阵时,频繁计算某一子矩阵的和是一个常见的操作。传统的做法是直接遍历该子矩阵,时间复杂度较高。当矩阵非常大且有大量的查询时,直接计算将变得低效。为了提高效率,我们可以通过 二维前缀和 技巧在常数时间内解决这个…...
鸢尾花书《编程不难》02---学习书本里面的三个案例
文章目录 1.引言2.第一个例子---模拟硬币的投掷结果3.第二个例子---混合两个一元高斯分布的随机数4.第三个例子---线性回归的作图5.关于书中的问题的解决方案 1.引言 今天的这个文章主要是阅读学习鸢尾花书系列的第一本《编程不难》,今天主要是记录下书里面的两个例…...
MySQL(高级特性篇) 13 章——事务基础知识
一、数据库事务概述 事务是数据库区别于文件系统的重要特性之一 (1)存储引擎支持情况 SHOW ENGINES命令来查看当前MySQL支持的存储引擎都有哪些,以及这些存储引擎是否支持事务能看出在MySQL中,只有InnoDB是支持事务的 &#x…...
CSS Display属性完全指南
CSS Display属性完全指南 引言核心概念常用display值详解1. block(块级元素)2. inline(行内元素)3. inline-block(行内块级元素)4. flex(弹性布局)5. grid(网格布局&…...
【机器学习篇】K-Means 算法详解:从理论到实践的全面解析
网罗开发 (小红书、快手、视频号同名) 大家好,我是 展菲,目前在上市企业从事人工智能项目研发管理工作,平时热衷于分享各种编程领域的软硬技能知识以及前沿技术,包括iOS、前端、Harmony OS、Java、Python等…...
IntelliJ IDEA远程开发代理远程服务器端口(免费内网穿透)
IntelliJ IDEA远程开发代理远程服务器端口(免费内网穿透)(JetBrains家的其他IDE应该也支持) 之前看到宇宙第一IDE VS Code好像默认代理了远程的端口,但是一直没找到IDEA的同类功能,这次终于发现了 以Intell…...
内核定时器3-用户空间定时器
用户空间定时器与内核定时器的关系 虽然用户空间定时器和内核定时器在实现上各自独立,但用户空间定时器通常依赖于内核定时器提供的基础设施。以下是具体关系: 依赖性 用户空间定时器的实现基于内核定时器。 例如,POSIX 定时器使用内核的 h…...
C++ 字面量深度解析:从基础到实战进阶
在 C 开发中,字面量(Literal)不仅是基础语法的一部分,更是提升代码可读性、安全性和性能的关键工具。本文将深入探讨 C 字面量的高级特性、最新标准支持(C11/14/17/20)以及实际开发中的应用技巧,…...
论文paper(更新...)
目录 是否rebuttal?rebuttal 技巧 是否rebuttal? 如果不rebuttal 肯定会拒稿,编辑也会给审稿人发信息,如下: Comment: Thanks for your efforts in reviewing this paper. The authors have neither submitted a rebu…...
变形金刚多元宇宙
1 涉及的公司 1.1 孩之宝HasBro 孩之宝与Takara签订协议后,孩之宝开始使用Takara的专利进行研发。 1.2 日本特佳丽Takara公司 特佳丽Takara Diaclone可变形恐龙的机器人玩具 Microman可变形汽车的机器人玩具 1.3 日本东映TOEI ANIMTION 1.4 美国漫威 为了推广玩具…...
HTTP协议的无状态和无连接
无连接 ①无连接的含义 这里所说的无连接并不是指不连接,客户与服务器之间的HTTP连接是一种一次性连接,它限制每次连接只处理一个请求,当服务器返回本次请求的应答后便立即关闭连接,下次请求再重新建立连接。这种一次性连接主要考…...
ASP.NET代码审计 SQL注入篇(简单记录)
sql注入,全局搜索 Request QueryString ToString() select select * aspx是设计页面,而aspx.cs是类页面,也就是说设计页面用到的类信息在这个页面里面,其实就是把设计和实现分离开来。 源码 using System; using System.Collect…...
毫秒级响应的VoIP中的系统组合推荐
在高并发、低延迟、毫秒级响应的 VoIP 场景中,选择合适的操作系统组合至关重要。以下是针对 Ubuntu linux-lowlatency、CentOS Stream kernel-rt 和 Debian 自定义 PREEMPT_RT 的详细对比及推荐: 1. 系统组合对比 特性Ubuntu linux-lowlatencyCentO…...
w186格障碍诊断系统spring boot设计与实现
🙊作者简介:多年一线开发工作经验,原创团队,分享技术代码帮助学生学习,独立完成自己的网站项目。 代码可以查看文章末尾⬇️联系方式获取,记得注明来意哦~🌹赠送计算机毕业设计600个选题excel文…...
shell -c
个人博客地址:shell -c | 一张假钞的真实世界 shell -c {string}:表示命令从-c后的字符串读取。在需要使用管道或者重定向需要sudo时很有用,如下: $ sudo find ../*/exportFiles -mtime 15 -name "*" | xargs -I {} r…...
(笔记+作业)书生大模型实战营春节卷王班---L1G3000 浦语提示词工程实践
学员闯关手册:https://aicarrier.feishu.cn/wiki/QtJnweAW1iFl8LkoMKGcsUS9nld 课程视频:https://www.bilibili.com/video/BV13U1VYmEUr/ 课程文档:https://github.com/InternLM/Tutorial/tree/camp4/docs/L0/Python 关卡作业:htt…...
文献学习笔记:中风醒脑液(FYTF-919)临床试验解读:有效还是无效?
【中风醒脑液(FYTF-919)临床试验解读:有效还是无效?】 在发表于 The Lancet (2024 年 11 月 30 日,第 404 卷)的临床研究《Traditional Chinese medicine FYTF-919 (Zhongfeng Xingnao oral pr…...
[2025CVPR]DeepVideo-R1:基于难度感知回归GRPO的视频强化微调框架详解
突破视频大语言模型推理瓶颈,在多个视频基准上实现SOTA性能 一、核心问题与创新亮点 1.1 GRPO在视频任务中的两大挑战 安全措施依赖问题 GRPO使用min和clip函数限制策略更新幅度,导致: 梯度抑制:当新旧策略差异过大时梯度消失收敛困难:策略无法充分优化# 传统GRPO的梯…...
C++实现分布式网络通信框架RPC(3)--rpc调用端
目录 一、前言 二、UserServiceRpc_Stub 三、 CallMethod方法的重写 头文件 实现 四、rpc调用端的调用 实现 五、 google::protobuf::RpcController *controller 头文件 实现 六、总结 一、前言 在前边的文章中,我们已经大致实现了rpc服务端的各项功能代…...
【WiFi帧结构】
文章目录 帧结构MAC头部管理帧 帧结构 Wi-Fi的帧分为三部分组成:MAC头部frame bodyFCS,其中MAC是固定格式的,frame body是可变长度。 MAC头部有frame control,duration,address1,address2,addre…...
MySQL 隔离级别:脏读、幻读及不可重复读的原理与示例
一、MySQL 隔离级别 MySQL 提供了四种隔离级别,用于控制事务之间的并发访问以及数据的可见性,不同隔离级别对脏读、幻读、不可重复读这几种并发数据问题有着不同的处理方式,具体如下: 隔离级别脏读不可重复读幻读性能特点及锁机制读未提交(READ UNCOMMITTED)允许出现允许…...
学校招生小程序源码介绍
基于ThinkPHPFastAdminUniApp开发的学校招生小程序源码,专为学校招生场景量身打造,功能实用且操作便捷。 从技术架构来看,ThinkPHP提供稳定可靠的后台服务,FastAdmin加速开发流程,UniApp则保障小程序在多端有良好的兼…...
自然语言处理——Transformer
自然语言处理——Transformer 自注意力机制多头注意力机制Transformer 虽然循环神经网络可以对具有序列特性的数据非常有效,它能挖掘数据中的时序信息以及语义信息,但是它有一个很大的缺陷——很难并行化。 我们可以考虑用CNN来替代RNN,但是…...
莫兰迪高级灰总结计划简约商务通用PPT模版
莫兰迪高级灰总结计划简约商务通用PPT模版,莫兰迪调色板清新简约工作汇报PPT模版,莫兰迪时尚风极简设计PPT模版,大学生毕业论文答辩PPT模版,莫兰迪配色总结计划简约商务通用PPT模版,莫兰迪商务汇报PPT模版,…...
Git常用命令完全指南:从入门到精通
Git常用命令完全指南:从入门到精通 一、基础配置命令 1. 用户信息配置 # 设置全局用户名 git config --global user.name "你的名字"# 设置全局邮箱 git config --global user.email "你的邮箱example.com"# 查看所有配置 git config --list…...
Web后端基础(基础知识)
BS架构:Browser/Server,浏览器/服务器架构模式。客户端只需要浏览器,应用程序的逻辑和数据都存储在服务端。 优点:维护方便缺点:体验一般 CS架构:Client/Server,客户端/服务器架构模式。需要单独…...
【p2p、分布式,区块链笔记 MESH】Bluetooth蓝牙通信 BLE Mesh协议的拓扑结构 定向转发机制
目录 节点的功能承载层(GATT/Adv)局限性: 拓扑关系定向转发机制定向转发意义 CG 节点的功能 节点的功能由节点支持的特性和功能决定。所有节点都能够发送和接收网格消息。节点还可以选择支持一个或多个附加功能,如 Configuration …...
