BZOJ4403 序列统计

题目描述

给定三个正整数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$个。

题意即求$\sum _{i=1}^n{C}_{r-l+i}^i$。因为$C_n^m=C_n^{n-m}$，所以

$$\sum _{i=1}^n{C}_{r-l+i}^i=\sum _{i=1}^n{C}_{r-l+i}^{r-l}$$

又因为

$$\sum _{i=m}^n{C}_i^m=C_{n+1}^{m+1}$$

所以

$$\sum _{i=1}^n{C}_{r-l+i}^{r-l}=(\sum _{i=0}^n{C}_{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;
}