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,是一种程序设计思想,这种思想把对象作为程序的基本单元。类是抽象的,对象是具体的,一种类包括其特定的数据或属性,以及操作数据的函数(方法…...
【JavaEE】-- HTTP
1. HTTP是什么? HTTP(全称为"超文本传输协议")是一种应用非常广泛的应用层协议,HTTP是基于TCP协议的一种应用层协议。 应用层协议:是计算机网络协议栈中最高层的协议,它定义了运行在不同主机上…...
黑马Mybatis
Mybatis 表现层:页面展示 业务层:逻辑处理 持久层:持久数据化保存 在这里插入图片描述 Mybatis快速入门 的新型路由方案。 它替代了传统的 <BrowserRouter>,支持更强大的数据加载和操作功能(如 loader 和…...
转转集团旗下首家二手多品类循环仓店“超级转转”开业
6月9日,国内领先的循环经济企业转转集团旗下首家二手多品类循环仓店“超级转转”正式开业。 转转集团创始人兼CEO黄炜、转转循环时尚发起人朱珠、转转集团COO兼红布林CEO胡伟琨、王府井集团副总裁祝捷等出席了开业剪彩仪式。 据「TMT星球」了解,“超级…...
TRS收益互换:跨境资本流动的金融创新工具与系统化解决方案
一、TRS收益互换的本质与业务逻辑 (一)概念解析 TRS(Total Return Swap)收益互换是一种金融衍生工具,指交易双方约定在未来一定期限内,基于特定资产或指数的表现进行现金流交换的协议。其核心特征包括&am…...
JDK 17 新特性
#JDK 17 新特性 /**************** 文本块 *****************/ python/scala中早就支持,不稀奇 String json “”" { “name”: “Java”, “version”: 17 } “”"; /**************** Switch 语句 -> 表达式 *****************/ 挺好的ÿ…...
MySQL中【正则表达式】用法
MySQL 中正则表达式通过 REGEXP 或 RLIKE 操作符实现(两者等价),用于在 WHERE 子句中进行复杂的字符串模式匹配。以下是核心用法和示例: 一、基础语法 SELECT column_name FROM table_name WHERE column_name REGEXP pattern; …...
汇编常见指令
汇编常见指令 一、数据传送指令 指令功能示例说明MOV数据传送MOV EAX, 10将立即数 10 送入 EAXMOV [EBX], EAX将 EAX 值存入 EBX 指向的内存LEA加载有效地址LEA EAX, [EBX4]将 EBX4 的地址存入 EAX(不访问内存)XCHG交换数据XCHG EAX, EBX交换 EAX 和 EB…...
今日学习:Spring线程池|并发修改异常|链路丢失|登录续期|VIP过期策略|数值类缓存
文章目录 优雅版线程池ThreadPoolTaskExecutor和ThreadPoolTaskExecutor的装饰器并发修改异常并发修改异常简介实现机制设计原因及意义 使用线程池造成的链路丢失问题线程池导致的链路丢失问题发生原因 常见解决方法更好的解决方法设计精妙之处 登录续期登录续期常见实现方式特…...
排序算法总结(C++)
目录 一、稳定性二、排序算法选择、冒泡、插入排序归并排序随机快速排序堆排序基数排序计数排序 三、总结 一、稳定性 排序算法的稳定性是指:同样大小的样本 **(同样大小的数据)**在排序之后不会改变原始的相对次序。 稳定性对基础类型对象…...
