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,是一种程序设计思想,这种思想把对象作为程序的基本单元。类是抽象的,对象是具体的,一种类包括其特定的数据或属性,以及操作数据的函数(方法…...

《从零掌握MIPI CSI-2: 协议精解与FPGA摄像头开发实战》-- CSI-2 协议详细解析 (一)
CSI-2 协议详细解析 (一) 1. CSI-2层定义(CSI-2 Layer Definitions) 分层结构 :CSI-2协议分为6层: 物理层(PHY Layer) : 定义电气特性、时钟机制和传输介质(导线&#…...
【位运算】消失的两个数字(hard)
消失的两个数字(hard) 题⽬描述:解法(位运算):Java 算法代码:更简便代码 题⽬链接:⾯试题 17.19. 消失的两个数字 题⽬描述: 给定⼀个数组,包含从 1 到 N 所有…...

[ICLR 2022]How Much Can CLIP Benefit Vision-and-Language Tasks?
论文网址:pdf 英文是纯手打的!论文原文的summarizing and paraphrasing。可能会出现难以避免的拼写错误和语法错误,若有发现欢迎评论指正!文章偏向于笔记,谨慎食用 目录 1. 心得 2. 论文逐段精读 2.1. Abstract 2…...

江苏艾立泰跨国资源接力:废料变黄金的绿色供应链革命
在华东塑料包装行业面临限塑令深度调整的背景下,江苏艾立泰以一场跨国资源接力的创新实践,重新定义了绿色供应链的边界。 跨国回收网络:废料变黄金的全球棋局 艾立泰在欧洲、东南亚建立再生塑料回收点,将海外废弃包装箱通过标准…...
unix/linux,sudo,其发展历程详细时间线、由来、历史背景
sudo 的诞生和演化,本身就是一部 Unix/Linux 系统管理哲学变迁的微缩史。来,让我们拨开时间的迷雾,一同探寻 sudo 那波澜壮阔(也颇为实用主义)的发展历程。 历史背景:su的时代与困境 ( 20 世纪 70 年代 - 80 年代初) 在 sudo 出现之前,Unix 系统管理员和需要特权操作的…...

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

图表类系列各种样式PPT模版分享
图标图表系列PPT模版,柱状图PPT模版,线状图PPT模版,折线图PPT模版,饼状图PPT模版,雷达图PPT模版,树状图PPT模版 图表类系列各种样式PPT模版分享:图表系列PPT模板https://pan.quark.cn/s/20d40aa…...
重启Eureka集群中的节点,对已经注册的服务有什么影响
先看答案,如果正确地操作,重启Eureka集群中的节点,对已经注册的服务影响非常小,甚至可以做到无感知。 但如果操作不当,可能会引发短暂的服务发现问题。 下面我们从Eureka的核心工作原理来详细分析这个问题。 Eureka的…...

vulnyx Blogger writeup
信息收集 arp-scan nmap 获取userFlag 上web看看 一个默认的页面,gobuster扫一下目录 可以看到扫出的目录中得到了一个有价值的目录/wordpress,说明目标所使用的cms是wordpress,访问http://192.168.43.213/wordpress/然后查看源码能看到 这…...
tomcat入门
1 tomcat 是什么 apache开发的web服务器可以为java web程序提供运行环境tomcat是一款高效,稳定,易于使用的web服务器tomcathttp服务器Servlet服务器 2 tomcat 目录介绍 -bin #存放tomcat的脚本 -conf #存放tomcat的配置文件 ---catalina.policy #to…...