长沙企业网站建设报价,衡水百度seo,zol软件下载,泰安城建吧题目描述
给定三个正整数N、L和R#xff0c;统计长度在1到N之间#xff0c;元素大小都在L到R之间的单调不降序列的数量。输出答案对106310^631063取模的结果。
输入
输入第一行包含一个整数T#xff0c;表示数据组数。 第2到第T1行每行包含三个整数N、L和R#xff0c;N、…题目描述
给定三个正整数N、L和R统计长度在1到N之间元素大小都在L到R之间的单调不降序列的数量。输出答案对106310^631063取模的结果。
输入
输入第一行包含一个整数T表示数据组数。 第2到第T1行每行包含三个整数N、L和RN、L和R的意义如题所述。 1≤N,L,R≤10^91≤T≤100输入数据保证L≤R。
输出
输出包含T行每行有一个数字表示你所求出的答案对106310^631063取模的结果。
样例输入
2
1 4 5
2 4 5样例输出
2
5题解
前置知识lucas定理
在区间[l,r][l,r][l,r]中长度为nnn的单调不降序列的数量即Cr−l1n−1nCr−lnnC_{r-l1n-1}^nC_{r-ln}^nCr−l1n−1nCr−lnn个。
题意即求∑i1nCr−lii\sum\limits_{i1}^nC_{r-li}^ii1∑nCr−lii。因为CnmCnn−mC_n^mC_n^{n-m}CnmCnn−m所以
∑i1nCr−lii∑i1nCr−lir−l\sum\limits_{i1}^nC_{r-li}^i\sum\limits_{i1}^nC_{r-li}^{r-l}i1∑nCr−liii1∑nCr−lir−l
又因为
∑imnCimCn1m1\sum\limits_{im}^nC_i^mC_{n1}^{m1}im∑nCimCn1m1
所以
∑i1nCr−lir−l(∑i0nCr−lir−l)−1Cr−ln1r−l1−1Cr−ln1n−1\sum\limits_{i1}^nC_{r-li}^{r-l}(\sum\limits_{i0}^nC_{r-li}^{r-l})-1C_{r-ln1}^{r-l1}-1C_{r-ln1}^n-1i1∑nCr−lir−l(i0∑nCr−lir−l)−1Cr−ln1r−l1−1Cr−ln1n−1
Cr−ln1n−1C_{r-ln1}^n-1Cr−ln1n−1即为答案用lucas定理求出即可。
code
#includebits/stdc.h
using namespace std;
int n;
long long vt1,x,y,ans0,a[15],b[15];
void exgcd(long long c,long long d){if(d0){x1;y0;return;}exgcd(d,c%d);long long tx;xy;yt-c/d*y;
}
int main()
{scanf(%d,n);for(int i1;in;i){scanf(%lld%lld,a[i],b[i]);vtvt*a[i];}for(int i1;in;i){exgcd(vt/a[i],a[i]);x(x%a[i]a[i])%a[i];ans(ansvt/a[i]*b[i]*x%vt)%vt;}printf(%lld,ans);return 0;
}
