【bzoj4403】【序列统计】不降转升+组合数添项合并
2024-08-23 14:31:32
(上不了p站我要死了,侵权度娘背锅)
Description
给定三个正整数N、L和R,统计长度在1到N之间,元素大小都在L到R之间的单调不降序列的数量。输出答案对10^6+3取模的结果。
Input
输入第一行包含一个整数T,表示数据组数。
第2到第T+1行每行包含三个整数N、L和R,N、L和R的意义如题所述。
1≤N,L,R≤10^9,1≤T≤100,输入数据保证L≤R。
Output
输出包含T行,每行有一个数字,表示你所求出的答案对10^6+3取模的结果。
Sample Input
2
1 4 5
2 4 5
Sample Output
2
5
//【样例说明】满足条件的2个序列为[4]和[5]。
好吧。。。我自己根本想不出来
如果单调不降难以求出来,而单调上升很容易求出来,那么为什么不把单调不降转为单调上升呢?
把第i位加上i,于是就将问题转为了在[l+1,r+n]中选n个不同的数出来,按从小到大的顺序排列。方案数为C(r-l+n,n)。
然后要求长度为1~n的方案数
全部列出来:
很是巧妙啊
组合数中的添项拆项(C(n,1)=C(n,n)=1)化项(C(n,n)=C(n+1,n+1))的运用,通常都是向递推式C(n,m)=C(n-1,m)+C(n-1,m-1)看齐。
代码(记得处理负数)
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#ifdef WIN32
#define RIN "%I64d"
#else
#define RIN "%lld"
#endif
#define ll long long
template <typename T>inline void read(T &res){
T k=1,x=0;char ch=0;
while(ch<'0'||ch>'9'){if(ch=='-')k=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
res=k*x;
}
const ll mod=1e6+3;
ll jiec[mod+7],niy[mod+7];
ll n,l,r;
void exgcd(ll a,ll b,ll &x,ll &y){
if(b==0){
x=1,y=0;
return ;
}
ll x0,y0;
exgcd(b,a%b,x0,y0);
x=y0;
y=x0-(a/b)*y0;
}
ll inverse(ll a){
ll x,y;
exgcd(a,mod,x,y);
return (x%mod+mod)%mod;
}
void init(){
jiec[0]=niy[0]=1;
for(int i=1;i<mod;i++) jiec[i]=jiec[i-1]*i%mod;
niy[mod-1]=inverse(jiec[mod-1]);
for(int i=mod-2;i>=1;i--) niy[i]=niy[i+1]*(i+1)%mod;
}
ll comb(ll a,ll b){
return jiec[a]*niy[b]%mod*niy[a-b]%mod;
}
ll lucas(ll a,ll b){
if(a<b) return 0;
if(a==0&&b==0) return 1;
if(a<mod&&b<mod) return comb(a,b);
return lucas(a/mod,b/mod)*lucas(a%mod,b%mod)%mod;
}
void solve(){
read(n),read(l),read(r);
printf(RIN"\n",(lucas(r-l+n+1,n)-1+mod)%mod);
}
int main(){
init();
int t;
read(t);
while(t--) solve();
return 0;
}
最新文章
- 整合struts2+hibernate详细配置步骤及注意事项
- iOS 字号转换问题
- 生产uuid
- linux 重命名文件和文件夹
- Python学习教程(learning Python)--2.2.2 Python全局和局部变量
- jquery 常用组件的小代码
- 初识CSS3之媒体查询(2015年05月31日)
- 编译安装php时提示Cannot find MySQL header files的解决方法
- php把excel数值格式转成日期格式问题
- mahout源码分析之Decision Forest 三部曲之二BuildForest(1)
- ctype.h
- gradle 打包springboot项目,找不到项目jar application.class
- rabbitmq的五种工作模式
- 设计模式笔记:单一职责原则(SRP, Single Responsibility Principle)
- 08 Zabbix Item类型之Zabbix agent类型
- [No0000C0]百度网盘真实地址解析(不用下载百度网盘)20170301
- JS实现document.ready
- Python之路 - 网络编程之粘包
- [日常] Go语言圣经--结构体,JSON习题
- Java初始化顺序(静态变量、静态初始化块、实例变量、实例初始化块、构造方法)
热门文章
- Java基础-7数组
- dpkg.cfg
- HDU 2295 Radar (二分 + Dancing Links 重复覆盖模型 )
- 安卓自动化robotium工具简单使用(二)
- Spring MVC表单标签
- Servlet 中 RequestDispacher 请求与分发
- Error: could not find java.dll 解决办法
- 命令__shell变量$#,$@,$0,$1,$2的含义解释
- 【CF Round 439 E. The Untended Antiquity】
- 一键GHOST