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

【算组合数】CF1833 F

少见地秒了这道1700,要是以后都这样就好了.... 

Problem - F - Codeforces

题意:

给定一个数列,让你在这个数列里找一个大小为M的子集,使得极差不超过M

 

思路:

子集,不是子序列,说明和顺序无关,因此可以考虑排序

观察一下样例可知,排序后我们可以双指针一下,然后方案数就是区间map之积

 

Code:

#include <bits/stdc++.h>#define int long longusing namespace std;const int mxn=2e5+10;
const int mxe=2e5+10;
const int mod=1e9+7;map<int,int> mp;int N,M;
int len=0;
int a[mxn],b[mxn],c[mxn],pre[mxn];int ksm(int a,int b,int mod){int res=1ll;while(b){if(b&1) res=(res*a)%mod;a=(a*a)%mod;b>>=1;}return res;
}
void solve(){mp.clear();len=0;cin>>N>>M;set<int> S;for(int i=1;i<=N;i++){cin>>a[i];S.insert(a[i]);mp[a[i]]++;}for(auto it:S) b[++len]=it; for(int i=1;i<=len;i++) c[i]=mp[b[i]];pre[0]=1;for(int i=1;i<=len;i++) pre[i]=pre[i-1]*c[i]%mod;int r=1;int ans=0;for(int l=1;l<=len;l++){while(r<=len&&b[r]-b[l]<M&&r-l+1<=M) r++;if(r-1-l+1==M&&b[r-1]-b[l]<M) ans+=pre[r-1]*ksm(pre[l-1],mod-2,mod)%mod;}cout<<ans%mod<<'\n';
}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int __=1;cin>>__;while(__--)solve();return 0; 
}

相关文章:

【算组合数】CF1833 F

少见地秒了这道1700&#xff0c;要是以后都这样就好了.... Problem - F - Codeforces 题意&#xff1a; 给定一个数列&#xff0c;让你在这个数列里找一个大小为M的子集&#xff0c;使得极差不超过M 思路&#xff1a; 子集&#xff0c;不是子序列&#xff0c;说明和顺序无…...

Attention详解(自用)

encoder-decoder 分心模型&#xff1a;没有引入注意力的模型在输入句子比较短的时候问题不大&#xff0c;但是如果输入句子比较长&#xff0c;此时所有语义完全通过一个中间语义向量来表示&#xff0c;单词自身的信息已经消失&#xff0c;可想而知会丢失很多细节信息&#xff0…...

pptx转pdf工具类

引入依赖 <dependency><groupId>org.apache.poi</groupId><artifactId>poi</artifactId><version>5.0.0</version></dependency><dependency><groupId>org.apache.poi</groupId><artifactId>poi-ooxm…...

2023华为OD统一考试(B卷)题库清单(持续收录中)以及考点说明

目录 专栏导读2023 B卷 “新加题”&#xff08;100分值&#xff09;2023Q2 100分2023Q2 200分2023Q1 100分2023Q1 200分2022Q4 100分2022Q4 200分牛客练习题 专栏导读 本专栏收录于《华为OD机试&#xff08;JAVA&#xff09;真题&#xff08;A卷B卷&#xff09;》。 刷的越多&…...

论文笔记--Won’t Get Fooled Again: Answering Questions with False Premises

论文笔记--Won’t Get Fooled Again: Answering Questions with False Premises 1. 文章简介2. 文章概括3 文章重点技术3.1 大模型面对FPQs的表现3.2 False QAs数据集3.3 训练和评估 4. 文章亮点5. 原文传送门 1. 文章简介 标题&#xff1a;Won’t Get Fooled Again: Answerin…...

【Django】include app_name和namespace的区别

app_name 区分不同app的url的name&#xff0c;防止不同app之间&#xff0c;url_name的重名&#xff0c;引用时加入app_name:name namespace 区分不同路由 include同一个view module的情况&#xff0c; 让不同路由进入同一个view中&#xff0c;进行reverse时&#xff0c;根据对…...

(黑客)自学笔记

特别声明&#xff1a; 此教程为纯技术分享&#xff01;本教程的目的决不是为那些怀有不良动机的人提供及技术支持&#xff01;也不承担因为技术被滥用所产生的连带责任&#xff01;本教程的目的在于最大限度地唤醒大家对网络安全的重视&#xff0c;并采取相应的安全措施&#x…...

【期末课程设计】学生成绩管理系统

因其独特&#xff0c;因其始终如一 文章目录 一、学生成绩管理系统介绍 二、学生成绩管理系统设计思路 三、源代码 1. test.c 2. Student Management System.c 3.Stu_System.c 4.Teacher.c 5.Student Management System.h 前言&#xff1a; 学生成绩管理系统含教师…...

【论文笔记】KDD2019 | KGAT: Knowledge Graph Attention Network for Recommendation

Abstract 为了更好的推荐&#xff0c;不仅要对user-item交互进行建模&#xff0c;还要将关系信息考虑进来 传统方法因子分解机将每个交互都当作一个独立的实例&#xff0c;但是忽略了item之间的关系&#xff08;eg&#xff1a;一部电影的导演也是另一部电影的演员&#xff09…...

ES6:基础使用,积累

一、理解ES6 ES6是ECMAScript 6.0的简称&#xff0c;也被称为ES2015。它是ECMAScript的第六个版本&#xff0c;是JavaScript标准的下一个重大更新。ES6于2015年6月发布&#xff0c;新增了许多新的语言特性和API&#xff0c;包括箭头函数、let和const关键字、模板字符串、解构赋…...

Android端上传文件到Spring Boot后端

准备 确定好服务器端文件保存的位置确定好请求参数名&#xff08;前后端要保持一致的喔&#xff09;如果手机是通过usb连接到电脑的&#xff0c;需要执行一下&#xff1a; adb reverse tcp:8080 tcp:8080 AndroidManifest.xml的<application/>节点中加上: android:usesC…...

使用GGML和LangChain在CPU上运行量化的llama2

Meta AI 在本周二发布了最新一代开源大模型 Llama 2。对比于今年 2 月发布的 Llama 1&#xff0c;训练所用的 token 翻了一倍&#xff0c;已经达到了 2 万亿&#xff0c;对于使用大模型最重要的上下文长度限制&#xff0c;Llama 2 也翻了一倍。 在本文&#xff0c;我们将紧跟趋…...

微服务基础理论

微服务简介 微服务Microservices之父&#xff0c;马丁.福勒&#xff0c;对微服务大概的概述如下&#xff1a; 就目前而言&#xff0c;对于微服务业界并没有一个统一的、标准的定义&#xff08;While there is no precise definition of this architectural style ) 。但通在其…...

《向量数据库指南》:向量数据库Pinecone管理数据教程

目录 连接到索引 指定索引端点 调用whoami以检索您的项目名称。 描述索引统计信息 获取向量 更新向量 完整更新 ℹ️注意 部分更新 ⚠️注意 ℹ️注意 删除向量...

以深度为基础的Scikit-learn: 高级特性与最佳实践

Scikit-learn是一个广受欢迎的Python库&#xff0c;它用于解决许多机器学习的问题。在本篇文章中&#xff0c;我们将进一步探索Scikit-learn的高级特性和最佳实践。 一、管道机制 Scikit-learn的Pipeline类是一种方便的工具&#xff0c;它允许你将多个步骤&#xff08;如数据…...

Autosar MCAL-S32K324Dio配置-基于EB

文章目录 DioPost Build Variant UsedConfig VariantDioConfigDioPortDioChannelDioChannelGroupDioConfigDio Development Error DetectSIUL2 IP Dio Development Error DetectDio Version Info ApiDio Reverse Port BitsDio Flip Channel ApiDio Rea...

【Spring Boot】单元测试

单元测试 单元测试在日常项目开发中必不可少&#xff0c;Spring Boot提供了完善的单元测试框架和工具用于测试开发的应用。接下来介绍Spring Boot为单元测试提供了哪些支持&#xff0c;以及如何在Spring Boot项目中进行单元测试。 1.Spring Boot集成单元测试 单元测试主要用…...

Flink CEP (一)原理及概念

目录 1.Flink CEP 原理 2.Flink API开发 2.1 模式 pattern 2.2 模式 pattern属性 2.3 模式间的关系 1.Flink CEP 原理 Flink CEP内部是用NFA&#xff08;非确定有限自动机&#xff09;来实现的&#xff0c;由点和边组成的一个状态图&#xff0c;以一个初始状态作为起点&am…...

vue3+taro+Nutui 开发小程序(二)

上一篇我们初始化了小程序项目&#xff0c;这一篇我们来整理一下框架 首先可以看到我的项目整理框架是这样的&#xff1a; components:这里存放封装的组件 custom-tab-bar:这里存放自己封装的自定义tabbar interface&#xff1a;这里放置了Ts的一些基本泛型&#xff0c;不用…...

Transformer 模型实用介绍:BERT

动动发财的小手&#xff0c;点个赞吧&#xff01; 在 NLP 中&#xff0c;Transformer 模型架构是一场革命&#xff0c;极大地增强了理解和生成文本信息的能力。 在本教程[1]中&#xff0c;我们将深入研究 BERT&#xff08;一种著名的基于 Transformer 的模型&#xff09;&#…...

IDEA运行Tomcat出现乱码问题解决汇总

最近正值期末周&#xff0c;有很多同学在写期末Java web作业时&#xff0c;运行tomcat出现乱码问题&#xff0c;经过多次解决与研究&#xff0c;我做了如下整理&#xff1a; 原因&#xff1a; IDEA本身编码与tomcat的编码与Windows编码不同导致&#xff0c;Windows 系统控制台…...

应用升级/灾备测试时使用guarantee 闪回点迅速回退

1.场景 应用要升级,当升级失败时,数据库回退到升级前. 要测试系统,测试完成后,数据库要回退到测试前。 相对于RMAN恢复需要很长时间&#xff0c; 数据库闪回只需要几分钟。 2.技术实现 数据库设置 2个db_recovery参数 创建guarantee闪回点&#xff0c;不需要开启数据库闪回。…...

Unity3D中Gfx.WaitForPresent优化方案

前言 在Unity中&#xff0c;Gfx.WaitForPresent占用CPU过高通常表示主线程在等待GPU完成渲染&#xff08;即CPU被阻塞&#xff09;&#xff0c;这表明存在GPU瓶颈或垂直同步/帧率设置问题。以下是系统的优化方案&#xff1a; 对惹&#xff0c;这里有一个游戏开发交流小组&…...

SciencePlots——绘制论文中的图片

文章目录 安装一、风格二、1 资源 安装 # 安装最新版 pip install githttps://github.com/garrettj403/SciencePlots.git# 安装稳定版 pip install SciencePlots一、风格 简单好用的深度学习论文绘图专用工具包–Science Plot 二、 1 资源 论文绘图神器来了&#xff1a;一行…...

基于ASP.NET+ SQL Server实现(Web)医院信息管理系统

医院信息管理系统 1. 课程设计内容 在 visual studio 2017 平台上&#xff0c;开发一个“医院信息管理系统”Web 程序。 2. 课程设计目的 综合运用 c#.net 知识&#xff0c;在 vs 2017 平台上&#xff0c;进行 ASP.NET 应用程序和简易网站的开发&#xff1b;初步熟悉开发一…...

【Java学习笔记】Arrays类

Arrays 类 1. 导入包&#xff1a;import java.util.Arrays 2. 常用方法一览表 方法描述Arrays.toString()返回数组的字符串形式Arrays.sort()排序&#xff08;自然排序和定制排序&#xff09;Arrays.binarySearch()通过二分搜索法进行查找&#xff08;前提&#xff1a;数组是…...

论文浅尝 | 基于判别指令微调生成式大语言模型的知识图谱补全方法(ISWC2024)

笔记整理&#xff1a;刘治强&#xff0c;浙江大学硕士生&#xff0c;研究方向为知识图谱表示学习&#xff0c;大语言模型 论文链接&#xff1a;http://arxiv.org/abs/2407.16127 发表会议&#xff1a;ISWC 2024 1. 动机 传统的知识图谱补全&#xff08;KGC&#xff09;模型通过…...

如何在网页里填写 PDF 表格?

有时候&#xff0c;你可能希望用户能在你的网站上填写 PDF 表单。然而&#xff0c;这件事并不简单&#xff0c;因为 PDF 并不是一种原生的网页格式。虽然浏览器可以显示 PDF 文件&#xff0c;但原生并不支持编辑或填写它们。更糟的是&#xff0c;如果你想收集表单数据&#xff…...

React---day11

14.4 react-redux第三方库 提供connect、thunk之类的函数 以获取一个banner数据为例子 store&#xff1a; 我们在使用异步的时候理应是要使用中间件的&#xff0c;但是configureStore 已经自动集成了 redux-thunk&#xff0c;注意action里面要返回函数 import { configureS…...

Linux C语言网络编程详细入门教程:如何一步步实现TCP服务端与客户端通信

文章目录 Linux C语言网络编程详细入门教程&#xff1a;如何一步步实现TCP服务端与客户端通信前言一、网络通信基础概念二、服务端与客户端的完整流程图解三、每一步的详细讲解和代码示例1. 创建Socket&#xff08;服务端和客户端都要&#xff09;2. 绑定本地地址和端口&#x…...