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

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

题目

代码

#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版本 --- 改

前言&#xff1a; 通过实践而发现真理&#xff0c;又通过实践而证实真理和发展真理。从感性认识而能动地发展到理性认识&#xff0c;又从理性认识而能动地指导革命实践&#xff0c;改造主观世界和客观世界。实践、认识、再实践、再认识&#xff0c;这种形式&#xff0c;循环往…...

并发编程中的常见问题

1 竞态条件 (Race Condition) 定义:竞态条件是指多个线程在访问共享资源时,由于执行顺序的不同导致结果不确定的情况。 示例: public class Counter {private int count = 0;public void increment() {count++;}public int getCount() {return count;} }在多线程环境下,…...

二维前缀和:高效求解矩阵区域和问题

在处理二维矩阵时&#xff0c;频繁计算某一子矩阵的和是一个常见的操作。传统的做法是直接遍历该子矩阵&#xff0c;时间复杂度较高。当矩阵非常大且有大量的查询时&#xff0c;直接计算将变得低效。为了提高效率&#xff0c;我们可以通过 二维前缀和 技巧在常数时间内解决这个…...

鸢尾花书《编程不难》02---学习书本里面的三个案例

文章目录 1.引言2.第一个例子---模拟硬币的投掷结果3.第二个例子---混合两个一元高斯分布的随机数4.第三个例子---线性回归的作图5.关于书中的问题的解决方案 1.引言 今天的这个文章主要是阅读学习鸢尾花书系列的第一本《编程不难》&#xff0c;今天主要是记录下书里面的两个例…...

MySQL(高级特性篇) 13 章——事务基础知识

一、数据库事务概述 事务是数据库区别于文件系统的重要特性之一 &#xff08;1&#xff09;存储引擎支持情况 SHOW ENGINES命令来查看当前MySQL支持的存储引擎都有哪些&#xff0c;以及这些存储引擎是否支持事务能看出在MySQL中&#xff0c;只有InnoDB是支持事务的 &#x…...

CSS Display属性完全指南

CSS Display属性完全指南 引言核心概念常用display值详解1. block&#xff08;块级元素&#xff09;2. inline&#xff08;行内元素&#xff09;3. inline-block&#xff08;行内块级元素&#xff09;4. flex&#xff08;弹性布局&#xff09;5. grid&#xff08;网格布局&…...

【机器学习篇】K-Means 算法详解:从理论到实践的全面解析

网罗开发 &#xff08;小红书、快手、视频号同名&#xff09; 大家好&#xff0c;我是 展菲&#xff0c;目前在上市企业从事人工智能项目研发管理工作&#xff0c;平时热衷于分享各种编程领域的软硬技能知识以及前沿技术&#xff0c;包括iOS、前端、Harmony OS、Java、Python等…...

IntelliJ IDEA远程开发代理远程服务器端口(免费内网穿透)

IntelliJ IDEA远程开发代理远程服务器端口&#xff08;免费内网穿透&#xff09;&#xff08;JetBrains家的其他IDE应该也支持&#xff09; 之前看到宇宙第一IDE VS Code好像默认代理了远程的端口&#xff0c;但是一直没找到IDEA的同类功能&#xff0c;这次终于发现了 以Intell…...

内核定时器3-用户空间定时器

用户空间定时器与内核定时器的关系 虽然用户空间定时器和内核定时器在实现上各自独立&#xff0c;但用户空间定时器通常依赖于内核定时器提供的基础设施。以下是具体关系&#xff1a; 依赖性 用户空间定时器的实现基于内核定时器。 例如&#xff0c;POSIX 定时器使用内核的 h…...

C++ 字面量深度解析:从基础到实战进阶

在 C 开发中&#xff0c;字面量&#xff08;Literal&#xff09;不仅是基础语法的一部分&#xff0c;更是提升代码可读性、安全性和性能的关键工具。本文将深入探讨 C 字面量的高级特性、最新标准支持&#xff08;C11/14/17/20&#xff09;以及实际开发中的应用技巧&#xff0c…...

论文paper(更新...)

目录 是否rebuttal&#xff1f;rebuttal 技巧 是否rebuttal&#xff1f; 如果不rebuttal 肯定会拒稿&#xff0c;编辑也会给审稿人发信息&#xff0c;如下&#xff1a; Comment: Thanks for your efforts in reviewing this paper. The authors have neither submitted a rebu…...

变形金刚多元宇宙

1 涉及的公司 1.1 孩之宝HasBro 孩之宝与Takara签订协议后&#xff0c;孩之宝开始使用Takara的专利进行研发。 1.2 日本特佳丽Takara公司 特佳丽Takara Diaclone可变形恐龙的机器人玩具 Microman可变形汽车的机器人玩具 1.3 日本东映TOEI ANIMTION 1.4 美国漫威 为了推广玩具…...

HTTP协议的无状态和无连接

无连接 ①无连接的含义 这里所说的无连接并不是指不连接&#xff0c;客户与服务器之间的HTTP连接是一种一次性连接&#xff0c;它限制每次连接只处理一个请求&#xff0c;当服务器返回本次请求的应答后便立即关闭连接&#xff0c;下次请求再重新建立连接。这种一次性连接主要考…...

ASP.NET代码审计 SQL注入篇(简单记录)

sql注入&#xff0c;全局搜索 Request QueryString ToString() select select * aspx是设计页面&#xff0c;而aspx.cs是类页面&#xff0c;也就是说设计页面用到的类信息在这个页面里面&#xff0c;其实就是把设计和实现分离开来。 源码 using System; using System.Collect…...

毫秒级响应的VoIP中的系统组合推荐

在高并发、低延迟、毫秒级响应的 VoIP 场景中&#xff0c;选择合适的操作系统组合至关重要。以下是针对 Ubuntu linux-lowlatency、CentOS Stream kernel-rt 和 Debian 自定义 PREEMPT_RT 的详细对比及推荐&#xff1a; 1. 系统组合对比 特性Ubuntu linux-lowlatencyCentO…...

w186格障碍诊断系统spring boot设计与实现

&#x1f64a;作者简介&#xff1a;多年一线开发工作经验&#xff0c;原创团队&#xff0c;分享技术代码帮助学生学习&#xff0c;独立完成自己的网站项目。 代码可以查看文章末尾⬇️联系方式获取&#xff0c;记得注明来意哦~&#x1f339;赠送计算机毕业设计600个选题excel文…...

shell -c

个人博客地址&#xff1a;shell -c | 一张假钞的真实世界 shell -c {string}&#xff1a;表示命令从-c后的字符串读取。在需要使用管道或者重定向需要sudo时很有用&#xff0c;如下&#xff1a; $ sudo find ../*/exportFiles -mtime 15 -name "*" | xargs -I {} r…...

(笔记+作业)书生大模型实战营春节卷王班---L1G3000 浦语提示词工程实践

学员闯关手册&#xff1a;https://aicarrier.feishu.cn/wiki/QtJnweAW1iFl8LkoMKGcsUS9nld 课程视频&#xff1a;https://www.bilibili.com/video/BV13U1VYmEUr/ 课程文档&#xff1a;https://github.com/InternLM/Tutorial/tree/camp4/docs/L0/Python 关卡作业&#xff1a;htt…...

文献学习笔记:中风醒脑液(FYTF-919)临床试验解读:有效还是无效?

【中风醒脑液&#xff08;FYTF-919&#xff09;临床试验解读&#xff1a;有效还是无效&#xff1f;】 在发表于 The Lancet &#xff08;2024 年 11 月 30 日&#xff0c;第 404 卷&#xff09;的临床研究《Traditional Chinese medicine FYTF-919 (Zhongfeng Xingnao oral pr…...

k8s从入门到放弃之Ingress七层负载

k8s从入门到放弃之Ingress七层负载 在Kubernetes&#xff08;简称K8s&#xff09;中&#xff0c;Ingress是一个API对象&#xff0c;它允许你定义如何从集群外部访问集群内部的服务。Ingress可以提供负载均衡、SSL终结和基于名称的虚拟主机等功能。通过Ingress&#xff0c;你可…...

centos 7 部署awstats 网站访问检测

一、基础环境准备&#xff08;两种安装方式都要做&#xff09; bash # 安装必要依赖 yum install -y httpd perl mod_perl perl-Time-HiRes perl-DateTime systemctl enable httpd # 设置 Apache 开机自启 systemctl start httpd # 启动 Apache二、安装 AWStats&#xff0…...

vue3 字体颜色设置的多种方式

在Vue 3中设置字体颜色可以通过多种方式实现&#xff0c;这取决于你是想在组件内部直接设置&#xff0c;还是在CSS/SCSS/LESS等样式文件中定义。以下是几种常见的方法&#xff1a; 1. 内联样式 你可以直接在模板中使用style绑定来设置字体颜色。 <template><div :s…...

零基础设计模式——行为型模式 - 责任链模式

第四部分&#xff1a;行为型模式 - 责任链模式 (Chain of Responsibility Pattern) 欢迎来到行为型模式的学习&#xff01;行为型模式关注对象之间的职责分配、算法封装和对象间的交互。我们将学习的第一个行为型模式是责任链模式。 核心思想&#xff1a;使多个对象都有机会处…...

Golang——6、指针和结构体

指针和结构体 1、指针1.1、指针地址和指针类型1.2、指针取值1.3、new和make 2、结构体2.1、type关键字的使用2.2、结构体的定义和初始化2.3、结构体方法和接收者2.4、给任意类型添加方法2.5、结构体的匿名字段2.6、嵌套结构体2.7、嵌套匿名结构体2.8、结构体的继承 3、结构体与…...

基于Java+VUE+MariaDB实现(Web)仿小米商城

仿小米商城 环境安装 nodejs maven JDK11 运行 mvn clean install -DskipTestscd adminmvn spring-boot:runcd ../webmvn spring-boot:runcd ../xiaomi-store-admin-vuenpm installnpm run servecd ../xiaomi-store-vuenpm installnpm run serve 注意&#xff1a;运行前…...

MySQL 主从同步异常处理

阅读原文&#xff1a;https://www.xiaozaoshu.top/articles/mysql-m-s-update-pk MySQL 做双主&#xff0c;遇到的这个错误&#xff1a; Could not execute Update_rows event on table ... Error_code: 1032是 MySQL 主从复制时的经典错误之一&#xff0c;通常表示&#xff…...

boost::filesystem::path文件路径使用详解和示例

boost::filesystem::path 是 Boost 库中用于跨平台操作文件路径的类&#xff0c;封装了路径的拼接、分割、提取、判断等常用功能。下面是对它的使用详解&#xff0c;包括常用接口与完整示例。 1. 引入头文件与命名空间 #include <boost/filesystem.hpp> namespace fs b…...

CppCon 2015 学习:Simple, Extensible Pattern Matching in C++14

什么是 Pattern Matching&#xff08;模式匹配&#xff09; ❝ 模式匹配就是一种“描述式”的写法&#xff0c;不需要你手动判断、提取数据&#xff0c;而是直接描述你希望的数据结构是什么样子&#xff0c;系统自动判断并提取。❞ 你给的定义拆解&#xff1a; ✴ Instead of …...

从0开始学习R语言--Day17--Cox回归

Cox回归 在用医疗数据作分析时&#xff0c;最常见的是去预测某类病的患者的死亡率或预测他们的结局。但是我们得到的病人数据&#xff0c;往往会有很多的协变量&#xff0c;即使我们通过计算来减少指标对结果的影响&#xff0c;我们的数据中依然会有很多的协变量&#xff0c;且…...