当前位置: 首页 > news >正文

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}^nCrl+1+n1n=Crl+nn个。

题意即求∑i=1nCr−l+ii\sum\limits_{i=1}^nC_{r-l+i}^ii=1nCrl+ii。因为Cnm=Cnn−mC_n^m=C_n^{n-m}Cnm=Cnnm,所以

∑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=1nCrl+ii=i=1nCrl+irl

又因为

∑i=mnCim=Cn+1m+1\sum\limits_{i=m}^nC_i^m=C_{n+1}^{m+1}i=mnCim=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=1nCrl+irl=(i=0nCrl+irl)1=Crl+n+1rl+11=Crl+n+1n1

Cr−l+n+1n−1C_{r-l+n+1}^n-1Crl+n+1n1即为答案,用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&#xff0c;统计长度在1到N之间&#xff0c;元素大小都在L到R之间的单调不降序列的数量。输出答案对106310^631063取模的结果。 输入 输入第一行包含一个整数T&#xff0c;表示数据组数。 第2到第T1行每行包含三个整数N、L和R&#xff0c;N、…...

如何正确使用 钳位二极管

在电路设计中,经常遇到需要IO保护的场景,比如ADC采样,GPIO接收电平信号等。 常见的保护方法有分压,限幅,限流等。本次我们讨论限幅方法中的 钳位二极管。 我们以BAT54S为例,它的符号是这样的, 而在很多手册里,我们可以看到,一般是这样使用的: 因此,我设计了简化…...

【C语言进阶】动态内存管理

&#x1f466;个人主页&#xff1a;Weraphael ✍&#x1f3fb;作者简介&#xff1a;目前是C语言学习者 ✈️专栏&#xff1a;C语言航路 &#x1f40b; 希望大家多多支持&#xff0c;咱一起进步&#xff01;&#x1f601; 如果文章对你有帮助的话 欢迎 评论&#x1f4ac; 点赞&a…...

第一批因ChatGPT坐牢的人,已经上路了

大家好&#xff0c;我是 Jack。 ChatGPT 的火爆有目共睹&#xff0c;有人靠着它赚了第一桶金&#xff0c;也有人靠着它即将吃上第一顿牢饭。 任何一件东西的火爆&#xff0c;总会给一些聪明人带来机会。 艾尔登法环火的时候&#xff0c;一堆淘宝卖魂的&#xff1b;羊了个羊火…...

Eclipse下Maven的集成

Eclipse下Maven的集成 2.1指定本地maven环境 参考&#xff1a;Eclipse的Maven创建_叶书文的博客-CSDN博客_eclipse创建maven项目 指定用本地maven指定maven仓库设置和地址2.2创建maven项目 1.新建 2.目录设置 3.坐标设置&#xff08;随便写就行&#xff09; 4.目录结构 2.3配置…...

Elasticsearch7学习笔记(尚硅谷)

文章目录一、ElasticSearch概述1、ElasticSearch是什么2、全文搜索引擎3、ElasticSearch 和 Solr3.1 概述3.2 比较总结二、Elasticsearch入门1、Elasticsearch安装1.1 下载使用1.2 数据格式2、索引操作3、文档操作&#xff08;了解&#xff09;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安装教程&#xff08;环境搭建&#xff09;安装VS2022-Community&#xff0c; 勾选c进行安装安装cmake3.25, 勾选环境变量进行安装安装python2.7.18, 勾选环境变量进行安装下载cocos2dx4.0并解压配置cocos2dx:运行cmd,进入…...

剑指 Offer 53 - I. 在排序数组中查找数字 I

原题链接 难度&#xff1a;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提示&#xff1a; 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 内核最初只是由芬兰人林纳斯托瓦兹&#xff08;Linus Torvalds&#xff09;在赫尔辛基大学上学时出于个人爱好而编写的。 Linux 是一套免费使用和自由传播的类 Unix 操作系统&#xff0c;是一个基于 POSIX 和 UNIX 的多用户、多任务、支持多线程和多 CPU 的操作系统。 …...

java面试题-泛型异常反射

泛型1.什么是泛型&#xff1f;Java是一种强类型语言&#xff0c;数据类型在编译时必须确定。如果我们想要在代码中使用不同类型的数据&#xff0c;那么就需要为每种类型分别写出相应的代码。这样会导致代码冗长、重复&#xff0c;也不便于维护。为了解决这个问题&#xff0c;Ja…...

详细解读ChatGPT:如何调用ChatGPT的API接口到官方例子的说明以及GitHub上的源码应用和csdn集成的ChatGPT

文章目录1. 解读ChatGPT1.1 词语解释1.2 功能解读2. GitHub上ChatGPT的应用源码3. 调用ChatGPT的API4. 官方例子说明5. 集成ChatGPT自ChatGPT出来到如今&#xff0c;始终走在火热的道路上&#xff0c;如今日活用户破亿&#xff0c;他为何有如此大的魅力&#xff0c;深受广大用户…...

九龙证券|最新评级情况出炉,机构扎堆这一板块!聚氨酯龙头获得最多关注

本周算计254家上市公司获组织“买入型”评级。 电子板块评级组织扎堆 证券时报数据宝计算&#xff0c;2月13日至17日&#xff0c;A股市场53家组织算计进行347次评级&#xff0c;254家上市公司获“买入型”评级&#xff08;包含买入、增持、强烈推荐、推荐&#xff09;。 从申…...

考研复试机试 | C++ | 尽量不要用python,很多学校不支持

目录1.1打印日期 &#xff08;清华大学上机题&#xff09;题目&#xff1a;代码&#xff1a;1.2改一改&#xff1a;上一题反过来问题代码&#xff1a;2.Day of Week &#xff08;上交&&清华机试题&#xff09;题目&#xff1a;代码&#xff1a;3.剩下的树&#xff08;清…...

ChatGPT时代,别再折腾孩子了

今天这篇完全是从两件事儿有感而发。昨天在文印店&#xff0c;在复印机上看到装订好的几页纸&#xff0c;我瞥了一眼&#xff0c;是历史知识点&#xff1a;隋朝大运河分为四段&#xff0c;分别是___ ___ ___ ___&#xff0c;连接了五大河___ ___ ___ ___ ______ 年&#xff…...

万字干货 | 荔枝魔方基于云原生的架构设计与实践

近年来&#xff0c;荔枝集团在国内和海外的业务迅速发展&#xff0c;业务数据规模也是成几何式地增长&#xff0c;海量数据的计算分析场景、业务智能算法应用需求随之而生&#xff0c;为了快速地满足业务发展的需要&#xff0c;我们面临着诸多的技术挑战。技术挑战工程问题资源…...

#科研筑基# python初学自用笔记 第九篇 面向对象编程

面向对象编程 Object Oriented Programming &#xff0c;简称OOP&#xff0c;是一种程序设计思想&#xff0c;这种思想把对象作为程序的基本单元。类是抽象的&#xff0c;对象是具体的&#xff0c;一种类包括其特定的数据或属性&#xff0c;以及操作数据的函数&#xff08;方法…...

《从零掌握MIPI CSI-2: 协议精解与FPGA摄像头开发实战》-- CSI-2 协议详细解析 (一)

CSI-2 协议详细解析 (一&#xff09; 1. CSI-2层定义&#xff08;CSI-2 Layer Definitions&#xff09; 分层结构 &#xff1a;CSI-2协议分为6层&#xff1a; 物理层&#xff08;PHY Layer&#xff09; &#xff1a; 定义电气特性、时钟机制和传输介质&#xff08;导线&#…...

【位运算】消失的两个数字(hard)

消失的两个数字&#xff08;hard&#xff09; 题⽬描述&#xff1a;解法&#xff08;位运算&#xff09;&#xff1a;Java 算法代码&#xff1a;更简便代码 题⽬链接&#xff1a;⾯试题 17.19. 消失的两个数字 题⽬描述&#xff1a; 给定⼀个数组&#xff0c;包含从 1 到 N 所有…...

[ICLR 2022]How Much Can CLIP Benefit Vision-and-Language Tasks?

论文网址&#xff1a;pdf 英文是纯手打的&#xff01;论文原文的summarizing and paraphrasing。可能会出现难以避免的拼写错误和语法错误&#xff0c;若有发现欢迎评论指正&#xff01;文章偏向于笔记&#xff0c;谨慎食用 目录 1. 心得 2. 论文逐段精读 2.1. Abstract 2…...

江苏艾立泰跨国资源接力:废料变黄金的绿色供应链革命

在华东塑料包装行业面临限塑令深度调整的背景下&#xff0c;江苏艾立泰以一场跨国资源接力的创新实践&#xff0c;重新定义了绿色供应链的边界。 跨国回收网络&#xff1a;废料变黄金的全球棋局 艾立泰在欧洲、东南亚建立再生塑料回收点&#xff0c;将海外废弃包装箱通过标准…...

unix/linux,sudo,其发展历程详细时间线、由来、历史背景

sudo 的诞生和演化,本身就是一部 Unix/Linux 系统管理哲学变迁的微缩史。来,让我们拨开时间的迷雾,一同探寻 sudo 那波澜壮阔(也颇为实用主义)的发展历程。 历史背景:su的时代与困境 ( 20 世纪 70 年代 - 80 年代初) 在 sudo 出现之前,Unix 系统管理员和需要特权操作的…...

QT: `long long` 类型转换为 `QString` 2025.6.5

在 Qt 中&#xff0c;将 long long 类型转换为 QString 可以通过以下两种常用方法实现&#xff1a; 方法 1&#xff1a;使用 QString::number() 直接调用 QString 的静态方法 number()&#xff0c;将数值转换为字符串&#xff1a; long long value 1234567890123456789LL; …...

图表类系列各种样式PPT模版分享

图标图表系列PPT模版&#xff0c;柱状图PPT模版&#xff0c;线状图PPT模版&#xff0c;折线图PPT模版&#xff0c;饼状图PPT模版&#xff0c;雷达图PPT模版&#xff0c;树状图PPT模版 图表类系列各种样式PPT模版分享&#xff1a;图表系列PPT模板https://pan.quark.cn/s/20d40aa…...

重启Eureka集群中的节点,对已经注册的服务有什么影响

先看答案&#xff0c;如果正确地操作&#xff0c;重启Eureka集群中的节点&#xff0c;对已经注册的服务影响非常小&#xff0c;甚至可以做到无感知。 但如果操作不当&#xff0c;可能会引发短暂的服务发现问题。 下面我们从Eureka的核心工作原理来详细分析这个问题。 Eureka的…...

vulnyx Blogger writeup

信息收集 arp-scan nmap 获取userFlag 上web看看 一个默认的页面&#xff0c;gobuster扫一下目录 可以看到扫出的目录中得到了一个有价值的目录/wordpress&#xff0c;说明目标所使用的cms是wordpress&#xff0c;访问http://192.168.43.213/wordpress/然后查看源码能看到 这…...

tomcat入门

1 tomcat 是什么 apache开发的web服务器可以为java web程序提供运行环境tomcat是一款高效&#xff0c;稳定&#xff0c;易于使用的web服务器tomcathttp服务器Servlet服务器 2 tomcat 目录介绍 -bin #存放tomcat的脚本 -conf #存放tomcat的配置文件 ---catalina.policy #to…...