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

BZOJ4403 序列统计

news 2025/9/14 18:02:29

题目描述

给定三个正整数N、L和R，统计长度在1到N之间，元素大小都在L到R之间的单调不降序列的数量。输出答案对 $10^6+3$ 取模的结果。

输入

输入第一行包含一个整数T，表示数据组数。
第2到第T+1行每行包含三个整数N、L和R，N、L和R的意义如题所述。
1≤N,L,R≤10^9，1≤T≤100，输入数据保证L≤R。

输出

输出包含T行，每行有一个数字，表示你所求出的答案对 $10^6+3$ 取模的结果。

样例输入

2
1 4 5
2 4 5

样例输出

2
5

题解

前置知识：lucas定理

在区间 $[l, r]$ 中长度为 $n$ 的单调不降序列的数量，即 $C_{r-l+1+n-1}^n=C_{r-l+n}^n$ 个。

题意即求 $∑i=1nCr−l+ii\sum\limits_{i=1}^nC_{r-l+i}^i$ 。因为 $C_n^m=C_n^{n-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=mnCim=Cn+1m+1\sum\limits_{i=m}^nC_i^m=C_{n+1}^{m+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-1$

$C_{r-l+n+1}^n-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;
}