BZOJ4403 序列统计
题目描述
给定三个正整数N、L和R,统计长度在1到N之间,元素大小都在L到R之间的单调不降序列的数量。输出答案对106+310^6+3106+3取模的结果。
输入
输入第一行包含一个整数T,表示数据组数。
第2到第T+1行每行包含三个整数N、L和R,N、L和R的意义如题所述。
1≤N,L,R≤10^9,1≤T≤100,输入数据保证L≤R。
输出
输出包含T行,每行有一个数字,表示你所求出的答案对106+310^6+3106+3取模的结果。
样例输入
2
1 4 5
2 4 5
样例输出
2
5
题解
前置知识:lucas定理
在区间[l,r][l,r][l,r]中长度为nnn的单调不降序列的数量,即Cr−l+1+n−1n=Cr−l+nnC_{r-l+1+n-1}^n=C_{r-l+n}^nCr−l+1+n−1n=Cr−l+nn个。
题意即求∑i=1nCr−l+ii\sum\limits_{i=1}^nC_{r-l+i}^ii=1∑nCr−l+ii。因为Cnm=Cnn−mC_n^m=C_n^{n-m}Cnm=Cnn−m,所以
∑i=1nCr−l+ii=∑i=1nCr−l+ir−l\sum\limits_{i=1}^nC_{r-l+i}^i=\sum\limits_{i=1}^nC_{r-l+i}^{r-l}i=1∑nCr−l+ii=i=1∑nCr−l+ir−l
又因为
∑i=mnCim=Cn+1m+1\sum\limits_{i=m}^nC_i^m=C_{n+1}^{m+1}i=m∑nCim=Cn+1m+1
所以
∑i=1nCr−l+ir−l=(∑i=0nCr−l+ir−l)−1=Cr−l+n+1r−l+1−1=Cr−l+n+1n−1\sum\limits_{i=1}^nC_{r-l+i}^{r-l}=(\sum\limits_{i=0}^nC_{r-l+i}^{r-l})-1=C_{r-l+n+1}^{r-l+1}-1=C_{r-l+n+1}^n-1i=1∑nCr−l+ir−l=(i=0∑nCr−l+ir−l)−1=Cr−l+n+1r−l+1−1=Cr−l+n+1n−1
Cr−l+n+1n−1C_{r-l+n+1}^n-1Cr−l+n+1n−1即为答案,用lucas定理求出即可。
code
#include<bits/stdc++.h>
using namespace std;
int n;
long long vt=1,x,y,ans=0,a[15],b[15];
void exgcd(long long c,long long d){if(d==0){x=1;y=0;return;}exgcd(d,c%d);long long t=x;x=y;y=t-c/d*y;
}
int main()
{scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%lld%lld",&a[i],&b[i]);vt=vt*a[i];}for(int i=1;i<=n;i++){exgcd(vt/a[i],a[i]);x=(x%a[i]+a[i])%a[i];ans=(ans+vt/a[i]*b[i]*x%vt)%vt;}printf("%lld",ans);return 0;
}
相关文章:
BZOJ4403 序列统计
题目描述 给定三个正整数N、L和R,统计长度在1到N之间,元素大小都在L到R之间的单调不降序列的数量。输出答案对106310^631063取模的结果。 输入 输入第一行包含一个整数T,表示数据组数。 第2到第T1行每行包含三个整数N、L和R,N、…...
如何正确使用 钳位二极管
在电路设计中,经常遇到需要IO保护的场景,比如ADC采样,GPIO接收电平信号等。 常见的保护方法有分压,限幅,限流等。本次我们讨论限幅方法中的 钳位二极管。 我们以BAT54S为例,它的符号是这样的, 而在很多手册里,我们可以看到,一般是这样使用的: 因此,我设计了简化…...
【C语言进阶】动态内存管理
👦个人主页:Weraphael ✍🏻作者简介:目前是C语言学习者 ✈️专栏:C语言航路 🐋 希望大家多多支持,咱一起进步!😁 如果文章对你有帮助的话 欢迎 评论💬 点赞&a…...
第一批因ChatGPT坐牢的人,已经上路了
大家好,我是 Jack。 ChatGPT 的火爆有目共睹,有人靠着它赚了第一桶金,也有人靠着它即将吃上第一顿牢饭。 任何一件东西的火爆,总会给一些聪明人带来机会。 艾尔登法环火的时候,一堆淘宝卖魂的;羊了个羊火…...
Eclipse下Maven的集成
Eclipse下Maven的集成 2.1指定本地maven环境 参考:Eclipse的Maven创建_叶书文的博客-CSDN博客_eclipse创建maven项目 指定用本地maven指定maven仓库设置和地址2.2创建maven项目 1.新建 2.目录设置 3.坐标设置(随便写就行) 4.目录结构 2.3配置…...
Elasticsearch7学习笔记(尚硅谷)
文章目录一、ElasticSearch概述1、ElasticSearch是什么2、全文搜索引擎3、ElasticSearch 和 Solr3.1 概述3.2 比较总结二、Elasticsearch入门1、Elasticsearch安装1.1 下载使用1.2 数据格式2、索引操作3、文档操作(了解)3.1 创建文档3.2 文档查询3.3 文档…...
前端学习第一阶段-第7章 品优购电商项目
7-1 品优购项目介绍及准备工作 01-品优购项目导读 02-网站制作流程 03-品优购项目规划 04-品优购项目搭建 05-品优购项目-样式的模块化开发 06-品优购项目-favicon图标制作 07-品优购项目-TDK三大标签SEO优化 7-2 首页Header区域实现 08-品优购首页-快捷导航shortcut结构搭建 0…...
cocos2dx 4.0 - cpp - pc版 环境搭建
开发环境vs2022 cocos2dx4.0 python2.7.18 cmake3.25安装教程(环境搭建)安装VS2022-Community, 勾选c进行安装安装cmake3.25, 勾选环境变量进行安装安装python2.7.18, 勾选环境变量进行安装下载cocos2dx4.0并解压配置cocos2dx:运行cmd,进入…...
剑指 Offer 53 - I. 在排序数组中查找数字 I
原题链接 难度:easy\color{Green}{easy}easy 题目描述 统计一个数字在排序数组中出现的次数。 示例 1: 输入: nums [5,7,7,8,8,10], target 8 输出: 2示例 2: 输入: nums [5,7,7,8,8,10], target 6 输出: 0提示: 0<nums.length<1050 <…...
华为OD机试 - 删除指定目录(Python) | 机试题算法思路 【2023】
最近更新的博客 华为OD机试 - 热点网络统计 | 备考思路,刷题要点,答疑 【新解法】 华为OD机试 - 查找单入口空闲区域 | 备考思路,刷题要点,答疑 【新解法】 华为OD机试 - 好朋友 | 备考思路,刷题要点,答疑 【新解法】 华为OD机试 - 找出同班小朋友 | 备考思路,刷题要点…...
PowerShell Install Office 2021 Pro Plus Viso Professional
前言 微软Office在很长一段时间内都是最常用和最受欢迎的软件。从小型创业公司到大公司,它的使用比例相当。它可以很容易地从微软的官方网站下载。但是,微软只提供安装程序,而不提供完整的软件供下载。这些安装文件通常比较小。下载并运行后,安装的文件将从后端服务器安装M…...
KubeSphere实战
文章目录一、KubeSphere平台安装1、Kubernetes上安装KubeSphere1.1 安装docker1.2 安装Kubernetes1.3 前置环境之nfs存储1.4 前置环境之metrics-server1.5 安装KubeSphere2、Linux单节点部署KubeSphere3、Linux多节点部署KubeSphere(推荐)二、KubeSphere实战1、多租户实战2、中…...
Linux 简介
Linux 内核最初只是由芬兰人林纳斯托瓦兹(Linus Torvalds)在赫尔辛基大学上学时出于个人爱好而编写的。 Linux 是一套免费使用和自由传播的类 Unix 操作系统,是一个基于 POSIX 和 UNIX 的多用户、多任务、支持多线程和多 CPU 的操作系统。 …...
java面试题-泛型异常反射
泛型1.什么是泛型?Java是一种强类型语言,数据类型在编译时必须确定。如果我们想要在代码中使用不同类型的数据,那么就需要为每种类型分别写出相应的代码。这样会导致代码冗长、重复,也不便于维护。为了解决这个问题,Ja…...
详细解读ChatGPT:如何调用ChatGPT的API接口到官方例子的说明以及GitHub上的源码应用和csdn集成的ChatGPT
文章目录1. 解读ChatGPT1.1 词语解释1.2 功能解读2. GitHub上ChatGPT的应用源码3. 调用ChatGPT的API4. 官方例子说明5. 集成ChatGPT自ChatGPT出来到如今,始终走在火热的道路上,如今日活用户破亿,他为何有如此大的魅力,深受广大用户…...
九龙证券|最新评级情况出炉,机构扎堆这一板块!聚氨酯龙头获得最多关注
本周算计254家上市公司获组织“买入型”评级。 电子板块评级组织扎堆 证券时报数据宝计算,2月13日至17日,A股市场53家组织算计进行347次评级,254家上市公司获“买入型”评级(包含买入、增持、强烈推荐、推荐)。 从申…...
考研复试机试 | C++ | 尽量不要用python,很多学校不支持
目录1.1打印日期 (清华大学上机题)题目:代码:1.2改一改:上一题反过来问题代码:2.Day of Week (上交&&清华机试题)题目:代码:3.剩下的树(清…...
ChatGPT时代,别再折腾孩子了
今天这篇完全是从两件事儿有感而发。昨天在文印店,在复印机上看到装订好的几页纸,我瞥了一眼,是历史知识点:隋朝大运河分为四段,分别是___ ___ ___ ___,连接了五大河___ ___ ___ ___ ______ 年ÿ…...
万字干货 | 荔枝魔方基于云原生的架构设计与实践
近年来,荔枝集团在国内和海外的业务迅速发展,业务数据规模也是成几何式地增长,海量数据的计算分析场景、业务智能算法应用需求随之而生,为了快速地满足业务发展的需要,我们面临着诸多的技术挑战。技术挑战工程问题资源…...
#科研筑基# python初学自用笔记 第九篇 面向对象编程
面向对象编程 Object Oriented Programming ,简称OOP,是一种程序设计思想,这种思想把对象作为程序的基本单元。类是抽象的,对象是具体的,一种类包括其特定的数据或属性,以及操作数据的函数(方法…...
设计模式和设计原则回顾
设计模式和设计原则回顾 23种设计模式是设计原则的完美体现,设计原则设计原则是设计模式的理论基石, 设计模式 在经典的设计模式分类中(如《设计模式:可复用面向对象软件的基础》一书中),总共有23种设计模式,分为三大类: 一、创建型模式(5种) 1. 单例模式(Sing…...
使用VSCode开发Django指南
使用VSCode开发Django指南 一、概述 Django 是一个高级 Python 框架,专为快速、安全和可扩展的 Web 开发而设计。Django 包含对 URL 路由、页面模板和数据处理的丰富支持。 本文将创建一个简单的 Django 应用,其中包含三个使用通用基本模板的页面。在此…...
Objective-C常用命名规范总结
【OC】常用命名规范总结 文章目录 【OC】常用命名规范总结1.类名(Class Name)2.协议名(Protocol Name)3.方法名(Method Name)4.属性名(Property Name)5.局部变量/实例变量(Local / Instance Variables&…...
Opencv中的addweighted函数
一.addweighted函数作用 addweighted()是OpenCV库中用于图像处理的函数,主要功能是将两个输入图像(尺寸和类型相同)按照指定的权重进行加权叠加(图像融合),并添加一个标量值&#x…...
镜像里切换为普通用户
如果你登录远程虚拟机默认就是 root 用户,但你不希望用 root 权限运行 ns-3(这是对的,ns3 工具会拒绝 root),你可以按以下方法创建一个 非 root 用户账号 并切换到它运行 ns-3。 一次性解决方案:创建非 roo…...
【2025年】解决Burpsuite抓不到https包的问题
环境:windows11 burpsuite:2025.5 在抓取https网站时,burpsuite抓取不到https数据包,只显示: 解决该问题只需如下三个步骤: 1、浏览器中访问 http://burp 2、下载 CA certificate 证书 3、在设置--隐私与安全--…...
基于Java+MySQL实现(GUI)客户管理系统
客户资料管理系统的设计与实现 第一章 需求分析 1.1 需求总体介绍 本项目为了方便维护客户信息为了方便维护客户信息,对客户进行统一管理,可以把所有客户信息录入系统,进行维护和统计功能。可通过文件的方式保存相关录入数据,对…...
Xela矩阵三轴触觉传感器的工作原理解析与应用场景
Xela矩阵三轴触觉传感器通过先进技术模拟人类触觉感知,帮助设备实现精确的力测量与位移监测。其核心功能基于磁性三维力测量与空间位移测量,能够捕捉多维触觉信息。该传感器的设计不仅提升了触觉感知的精度,还为机器人、医疗设备和制造业的智…...
【WebSocket】SpringBoot项目中使用WebSocket
1. 导入坐标 如果springboot父工程没有加入websocket的起步依赖,添加它的坐标的时候需要带上版本号。 <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-websocket</artifactId> </dep…...
当下AI智能硬件方案浅谈
背景: 现在大模型出来以后,打破了常规的机械式的对话,人机对话变得更聪明一点。 对话用到的技术主要是实时音视频,简称为RTC。下游硬件厂商一般都不会去自己开发音视频技术,开发自己的大模型。商用方案多见为字节、百…...
