【算组合数】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 的模型)&#…...
Mybatis逆向工程,动态创建实体类、条件扩展类、Mapper接口、Mapper.xml映射文件
今天呢,博主的学习进度也是步入了Java Mybatis 框架,目前正在逐步杨帆旗航。 那么接下来就给大家出一期有关 Mybatis 逆向工程的教学,希望能对大家有所帮助,也特别欢迎大家指点不足之处,小生很乐意接受正确的建议&…...
为什么需要建设工程项目管理?工程项目管理有哪些亮点功能?
在建筑行业,项目管理的重要性不言而喻。随着工程规模的扩大、技术复杂度的提升,传统的管理模式已经难以满足现代工程的需求。过去,许多企业依赖手工记录、口头沟通和分散的信息管理,导致效率低下、成本失控、风险频发。例如&#…...
鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院挂号小程序
一、开发准备 环境搭建: 安装DevEco Studio 3.0或更高版本配置HarmonyOS SDK申请开发者账号 项目创建: File > New > Create Project > Application (选择"Empty Ability") 二、核心功能实现 1. 医院科室展示 /…...
什么是库存周转?如何用进销存系统提高库存周转率?
你可能听说过这样一句话: “利润不是赚出来的,是管出来的。” 尤其是在制造业、批发零售、电商这类“货堆成山”的行业,很多企业看着销售不错,账上却没钱、利润也不见了,一翻库存才发现: 一堆卖不动的旧货…...
Python爬虫(二):爬虫完整流程
爬虫完整流程详解(7大核心步骤实战技巧) 一、爬虫完整工作流程 以下是爬虫开发的完整流程,我将结合具体技术点和实战经验展开说明: 1. 目标分析与前期准备 网站技术分析: 使用浏览器开发者工具(F12&…...
ElasticSearch搜索引擎之倒排索引及其底层算法
文章目录 一、搜索引擎1、什么是搜索引擎?2、搜索引擎的分类3、常用的搜索引擎4、搜索引擎的特点二、倒排索引1、简介2、为什么倒排索引不用B+树1.创建时间长,文件大。2.其次,树深,IO次数可怕。3.索引可能会失效。4.精准度差。三. 倒排索引四、算法1、Term Index的算法2、 …...
C# SqlSugar:依赖注入与仓储模式实践
C# SqlSugar:依赖注入与仓储模式实践 在 C# 的应用开发中,数据库操作是必不可少的环节。为了让数据访问层更加简洁、高效且易于维护,许多开发者会选择成熟的 ORM(对象关系映射)框架,SqlSugar 就是其中备受…...
【JavaSE】绘图与事件入门学习笔记
-Java绘图坐标体系 坐标体系-介绍 坐标原点位于左上角,以像素为单位。 在Java坐标系中,第一个是x坐标,表示当前位置为水平方向,距离坐标原点x个像素;第二个是y坐标,表示当前位置为垂直方向,距离坐标原点y个像素。 坐标体系-像素 …...
rnn判断string中第一次出现a的下标
# coding:utf8 import torch import torch.nn as nn import numpy as np import random import json""" 基于pytorch的网络编写 实现一个RNN网络完成多分类任务 判断字符 a 第一次出现在字符串中的位置 """class TorchModel(nn.Module):def __in…...
AI病理诊断七剑下天山,医疗未来触手可及
一、病理诊断困局:刀尖上的医学艺术 1.1 金标准背后的隐痛 病理诊断被誉为"诊断的诊断",医生需通过显微镜观察组织切片,在细胞迷宫中捕捉癌变信号。某省病理质控报告显示,基层医院误诊率达12%-15%,专家会诊…...
