当前位置: 首页 > 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;方法…...

Leetcode 3576. Transform Array to All Equal Elements

Leetcode 3576. Transform Array to All Equal Elements 1. 解题思路2. 代码实现 题目链接&#xff1a;3576. Transform Array to All Equal Elements 1. 解题思路 这一题思路上就是分别考察一下是否能将其转化为全1或者全-1数组即可。 至于每一种情况是否可以达到&#xf…...

C++ 求圆面积的程序(Program to find area of a circle)

给定半径r&#xff0c;求圆的面积。圆的面积应精确到小数点后5位。 例子&#xff1a; 输入&#xff1a;r 5 输出&#xff1a;78.53982 解释&#xff1a;由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982&#xff0c;因为我们只保留小数点后 5 位数字。 输…...

优选算法第十二讲:队列 + 宽搜 优先级队列

优选算法第十二讲&#xff1a;队列 宽搜 && 优先级队列 1.N叉树的层序遍历2.二叉树的锯齿型层序遍历3.二叉树最大宽度4.在每个树行中找最大值5.优先级队列 -- 最后一块石头的重量6.数据流中的第K大元素7.前K个高频单词8.数据流的中位数 1.N叉树的层序遍历 2.二叉树的锯…...

Java线上CPU飙高问题排查全指南

一、引言 在Java应用的线上运行环境中&#xff0c;CPU飙高是一个常见且棘手的性能问题。当系统出现CPU飙高时&#xff0c;通常会导致应用响应缓慢&#xff0c;甚至服务不可用&#xff0c;严重影响用户体验和业务运行。因此&#xff0c;掌握一套科学有效的CPU飙高问题排查方法&…...

比较数据迁移后MySQL数据库和OceanBase数据仓库中的表

设计一个MySQL数据库和OceanBase数据仓库的表数据比较的详细程序流程,两张表是相同的结构,都有整型主键id字段,需要每次从数据库分批取得2000条数据,用于比较,比较操作的同时可以再取2000条数据,等上一次比较完成之后,开始比较,直到比较完所有的数据。比较操作需要比较…...

第7篇:中间件全链路监控与 SQL 性能分析实践

7.1 章节导读 在构建数据库中间件的过程中&#xff0c;可观测性 和 性能分析 是保障系统稳定性与可维护性的核心能力。 特别是在复杂分布式场景中&#xff0c;必须做到&#xff1a; &#x1f50d; 追踪每一条 SQL 的生命周期&#xff08;从入口到数据库执行&#xff09;&#…...

在树莓派上添加音频输入设备的几种方法

在树莓派上添加音频输入设备可以通过以下步骤完成&#xff0c;具体方法取决于设备类型&#xff08;如USB麦克风、3.5mm接口麦克风或HDMI音频输入&#xff09;。以下是详细指南&#xff1a; 1. 连接音频输入设备 USB麦克风/声卡&#xff1a;直接插入树莓派的USB接口。3.5mm麦克…...

深度剖析 DeepSeek 开源模型部署与应用:策略、权衡与未来走向

在人工智能技术呈指数级发展的当下&#xff0c;大模型已然成为推动各行业变革的核心驱动力。DeepSeek 开源模型以其卓越的性能和灵活的开源特性&#xff0c;吸引了众多企业与开发者的目光。如何高效且合理地部署与运用 DeepSeek 模型&#xff0c;成为释放其巨大潜力的关键所在&…...

路由基础-路由表

本篇将会向读者介绍路由的基本概念。 前言 在一个典型的数据通信网络中&#xff0c;往往存在多个不同的IP网段&#xff0c;数据在不同的IP网段之间交互是需要借助三层设备的&#xff0c;这些设备具备路由能力&#xff0c;能够实现数据的跨网段转发。 路由是数据通信网络中最基…...

Unity-ECS详解

今天我们来了解Unity最先进的技术——ECS架构&#xff08;EntityComponentSystem&#xff09;。 Unity官方下有源码&#xff0c;我们下载源码后来学习。 ECS 与OOP&#xff08;Object-Oriented Programming&#xff09;对应&#xff0c;ECS是一种完全不同的编程范式与数据架构…...