当前位置: 首页 > 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;&#…...

java_网络服务相关_gateway_nacos_feign区别联系

1. spring-cloud-starter-gateway 作用&#xff1a;作为微服务架构的网关&#xff0c;统一入口&#xff0c;处理所有外部请求。 核心能力&#xff1a; 路由转发&#xff08;基于路径、服务名等&#xff09;过滤器&#xff08;鉴权、限流、日志、Header 处理&#xff09;支持负…...

(十)学生端搭建

本次旨在将之前的已完成的部分功能进行拼装到学生端&#xff0c;同时完善学生端的构建。本次工作主要包括&#xff1a; 1.学生端整体界面布局 2.模拟考场与部分个人画像流程的串联 3.整体学生端逻辑 一、学生端 在主界面可以选择自己的用户角色 选择学生则进入学生登录界面…...

【人工智能】神经网络的优化器optimizer(二):Adagrad自适应学习率优化器

一.自适应梯度算法Adagrad概述 Adagrad&#xff08;Adaptive Gradient Algorithm&#xff09;是一种自适应学习率的优化算法&#xff0c;由Duchi等人在2011年提出。其核心思想是针对不同参数自动调整学习率&#xff0c;适合处理稀疏数据和不同参数梯度差异较大的场景。Adagrad通…...

基于服务器使用 apt 安装、配置 Nginx

&#x1f9fe; 一、查看可安装的 Nginx 版本 首先&#xff0c;你可以运行以下命令查看可用版本&#xff1a; apt-cache madison nginx-core输出示例&#xff1a; nginx-core | 1.18.0-6ubuntu14.6 | http://archive.ubuntu.com/ubuntu focal-updates/main amd64 Packages ng…...

服务器硬防的应用场景都有哪些?

服务器硬防是指一种通过硬件设备层面的安全措施来防御服务器系统受到网络攻击的方式&#xff0c;避免服务器受到各种恶意攻击和网络威胁&#xff0c;那么&#xff0c;服务器硬防通常都会应用在哪些场景当中呢&#xff1f; 硬防服务器中一般会配备入侵检测系统和预防系统&#x…...

linux 错误码总结

1,错误码的概念与作用 在Linux系统中,错误码是系统调用或库函数在执行失败时返回的特定数值,用于指示具体的错误类型。这些错误码通过全局变量errno来存储和传递,errno由操作系统维护,保存最近一次发生的错误信息。值得注意的是,errno的值在每次系统调用或函数调用失败时…...

苍穹外卖--缓存菜品

1.问题说明 用户端小程序展示的菜品数据都是通过查询数据库获得&#xff0c;如果用户端访问量比较大&#xff0c;数据库访问压力随之增大 2.实现思路 通过Redis来缓存菜品数据&#xff0c;减少数据库查询操作。 缓存逻辑分析&#xff1a; ①每个分类下的菜品保持一份缓存数据…...

视频字幕质量评估的大规模细粒度基准

大家读完觉得有帮助记得关注和点赞&#xff01;&#xff01;&#xff01; 摘要 视频字幕在文本到视频生成任务中起着至关重要的作用&#xff0c;因为它们的质量直接影响所生成视频的语义连贯性和视觉保真度。尽管大型视觉-语言模型&#xff08;VLMs&#xff09;在字幕生成方面…...

html css js网页制作成品——HTML+CSS榴莲商城网页设计(4页)附源码

目录 一、&#x1f468;‍&#x1f393;网站题目 二、✍️网站描述 三、&#x1f4da;网站介绍 四、&#x1f310;网站效果 五、&#x1fa93; 代码实现 &#x1f9f1;HTML 六、&#x1f947; 如何让学习不再盲目 七、&#x1f381;更多干货 一、&#x1f468;‍&#x1f…...

JS设计模式(4):观察者模式

JS设计模式(4):观察者模式 一、引入 在开发中&#xff0c;我们经常会遇到这样的场景&#xff1a;一个对象的状态变化需要自动通知其他对象&#xff0c;比如&#xff1a; 电商平台中&#xff0c;商品库存变化时需要通知所有订阅该商品的用户&#xff1b;新闻网站中&#xff0…...