【算组合数】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,要是以后都这样就好了.... Problem - F - Codeforces 题意: 给定一个数列,让你在这个数列里找一个大小为M的子集,使得极差不超过M 思路: 子集,不是子序列,说明和顺序无…...
Attention详解(自用)
encoder-decoder 分心模型:没有引入注意力的模型在输入句子比较短的时候问题不大,但是如果输入句子比较长,此时所有语义完全通过一个中间语义向量来表示,单词自身的信息已经消失,可想而知会丢失很多细节信息࿰…...
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卷 “新加题”(100分值)2023Q2 100分2023Q2 200分2023Q1 100分2023Q1 200分2022Q4 100分2022Q4 200分牛客练习题 专栏导读 本专栏收录于《华为OD机试(JAVA)真题(A卷B卷)》。 刷的越多&…...
论文笔记--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. 文章简介 标题:Won’t Get Fooled Again: Answerin…...
【Django】include app_name和namespace的区别
app_name 区分不同app的url的name,防止不同app之间,url_name的重名,引用时加入app_name:name namespace 区分不同路由 include同一个view module的情况, 让不同路由进入同一个view中,进行reverse时,根据对…...
(黑客)自学笔记
特别声明: 此教程为纯技术分享!本教程的目的决不是为那些怀有不良动机的人提供及技术支持!也不承担因为技术被滥用所产生的连带责任!本教程的目的在于最大限度地唤醒大家对网络安全的重视,并采取相应的安全措施&#x…...
【期末课程设计】学生成绩管理系统
因其独特,因其始终如一 文章目录 一、学生成绩管理系统介绍 二、学生成绩管理系统设计思路 三、源代码 1. test.c 2. Student Management System.c 3.Stu_System.c 4.Teacher.c 5.Student Management System.h 前言: 学生成绩管理系统含教师…...
【论文笔记】KDD2019 | KGAT: Knowledge Graph Attention Network for Recommendation
Abstract 为了更好的推荐,不仅要对user-item交互进行建模,还要将关系信息考虑进来 传统方法因子分解机将每个交互都当作一个独立的实例,但是忽略了item之间的关系(eg:一部电影的导演也是另一部电影的演员)…...
ES6:基础使用,积累
一、理解ES6 ES6是ECMAScript 6.0的简称,也被称为ES2015。它是ECMAScript的第六个版本,是JavaScript标准的下一个重大更新。ES6于2015年6月发布,新增了许多新的语言特性和API,包括箭头函数、let和const关键字、模板字符串、解构赋…...
Android端上传文件到Spring Boot后端
准备 确定好服务器端文件保存的位置确定好请求参数名(前后端要保持一致的喔)如果手机是通过usb连接到电脑的,需要执行一下: adb reverse tcp:8080 tcp:8080 AndroidManifest.xml的<application/>节点中加上: android:usesC…...
使用GGML和LangChain在CPU上运行量化的llama2
Meta AI 在本周二发布了最新一代开源大模型 Llama 2。对比于今年 2 月发布的 Llama 1,训练所用的 token 翻了一倍,已经达到了 2 万亿,对于使用大模型最重要的上下文长度限制,Llama 2 也翻了一倍。 在本文,我们将紧跟趋…...
微服务基础理论
微服务简介 微服务Microservices之父,马丁.福勒,对微服务大概的概述如下: 就目前而言,对于微服务业界并没有一个统一的、标准的定义(While there is no precise definition of this architectural style ) 。但通在其…...
《向量数据库指南》:向量数据库Pinecone管理数据教程
目录 连接到索引 指定索引端点 调用whoami以检索您的项目名称。 描述索引统计信息 获取向量 更新向量 完整更新 ℹ️注意 部分更新 ⚠️注意 ℹ️注意 删除向量...
以深度为基础的Scikit-learn: 高级特性与最佳实践
Scikit-learn是一个广受欢迎的Python库,它用于解决许多机器学习的问题。在本篇文章中,我们将进一步探索Scikit-learn的高级特性和最佳实践。 一、管道机制 Scikit-learn的Pipeline类是一种方便的工具,它允许你将多个步骤(如数据…...
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】单元测试
单元测试 单元测试在日常项目开发中必不可少,Spring Boot提供了完善的单元测试框架和工具用于测试开发的应用。接下来介绍Spring Boot为单元测试提供了哪些支持,以及如何在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(非确定有限自动机)来实现的,由点和边组成的一个状态图,以一个初始状态作为起点&am…...
vue3+taro+Nutui 开发小程序(二)
上一篇我们初始化了小程序项目,这一篇我们来整理一下框架 首先可以看到我的项目整理框架是这样的: components:这里存放封装的组件 custom-tab-bar:这里存放自己封装的自定义tabbar interface:这里放置了Ts的一些基本泛型,不用…...
Transformer 模型实用介绍:BERT
动动发财的小手,点个赞吧! 在 NLP 中,Transformer 模型架构是一场革命,极大地增强了理解和生成文本信息的能力。 在本教程[1]中,我们将深入研究 BERT(一种著名的基于 Transformer 的模型)&#…...
观成科技:隐蔽隧道工具Ligolo-ng加密流量分析
1.工具介绍 Ligolo-ng是一款由go编写的高效隧道工具,该工具基于TUN接口实现其功能,利用反向TCP/TLS连接建立一条隐蔽的通信信道,支持使用Let’s Encrypt自动生成证书。Ligolo-ng的通信隐蔽性体现在其支持多种连接方式,适应复杂网…...
多模态2025:技术路线“神仙打架”,视频生成冲上云霄
文|魏琳华 编|王一粟 一场大会,聚集了中国多模态大模型的“半壁江山”。 智源大会2025为期两天的论坛中,汇集了学界、创业公司和大厂等三方的热门选手,关于多模态的集中讨论达到了前所未有的热度。其中,…...
前端导出带有合并单元格的列表
// 导出async function exportExcel(fileName "共识调整.xlsx") {// 所有数据const exportData await getAllMainData();// 表头内容let fitstTitleList [];const secondTitleList [];allColumns.value.forEach(column > {if (!column.children) {fitstTitleL…...
Frozen-Flask :将 Flask 应用“冻结”为静态文件
Frozen-Flask 是一个用于将 Flask 应用“冻结”为静态文件的 Python 扩展。它的核心用途是:将一个 Flask Web 应用生成成纯静态 HTML 文件,从而可以部署到静态网站托管服务上,如 GitHub Pages、Netlify 或任何支持静态文件的网站服务器。 &am…...
视频字幕质量评估的大规模细粒度基准
大家读完觉得有帮助记得关注和点赞!!! 摘要 视频字幕在文本到视频生成任务中起着至关重要的作用,因为它们的质量直接影响所生成视频的语义连贯性和视觉保真度。尽管大型视觉-语言模型(VLMs)在字幕生成方面…...
微信小程序云开发平台MySQL的连接方式
注:微信小程序云开发平台指的是腾讯云开发 先给结论:微信小程序云开发平台的MySQL,无法通过获取数据库连接信息的方式进行连接,连接只能通过云开发的SDK连接,具体要参考官方文档: 为什么? 因为…...
蓝桥杯3498 01串的熵
问题描述 对于一个长度为 23333333的 01 串, 如果其信息熵为 11625907.5798, 且 0 出现次数比 1 少, 那么这个 01 串中 0 出现了多少次? #include<iostream> #include<cmath> using namespace std;int n 23333333;int main() {//枚举 0 出现的次数//因…...
ABAP设计模式之---“简单设计原则(Simple Design)”
“Simple Design”(简单设计)是软件开发中的一个重要理念,倡导以最简单的方式实现软件功能,以确保代码清晰易懂、易维护,并在项目需求变化时能够快速适应。 其核心目标是避免复杂和过度设计,遵循“让事情保…...
Spring是如何解决Bean的循环依赖:三级缓存机制
1、什么是 Bean 的循环依赖 在 Spring框架中,Bean 的循环依赖是指多个 Bean 之间互相持有对方引用,形成闭环依赖关系的现象。 多个 Bean 的依赖关系构成环形链路,例如: 双向依赖:Bean A 依赖 Bean B,同时 Bean B 也依赖 Bean A(A↔B)。链条循环: Bean A → Bean…...
【VLNs篇】07:NavRL—在动态环境中学习安全飞行
项目内容论文标题NavRL: 在动态环境中学习安全飞行 (NavRL: Learning Safe Flight in Dynamic Environments)核心问题解决无人机在包含静态和动态障碍物的复杂环境中进行安全、高效自主导航的挑战,克服传统方法和现有强化学习方法的局限性。核心算法基于近端策略优化…...
