傳送門:4403: 序列統計
描述:
4403: 序列統計
Time Limit: 3 Sec Memory Limit: 128 MB
Submit: 414 Solved: 201
[ Submit][ Status][ Discuss]
Description
給定三個正整數N、L和R,統計長度在1到N之間,元素大小都在L到R之間的單調不降序列的數量。輸出答案對10^6+3取模的結果。
Input
輸入第一行包含一個整數T,表示資料組數。第2到第T+1行每行包含三個整數N、L和R,N、L和R的意義如題所述。
Output
輸出包含T行,每行有一個數字,表示你所求出的答案對106+3取模的結果。
Sample Input
2 1 4 5 2 4 5
Sample Output
25
HINT
提示
【樣例說明】滿足條件的2個序列為[4]和[5]。
【資料規模和約定】對于100%的資料,1≤N,L,R≤10^9,1≤T≤100,輸入資料保證L≤R。
Source
By yts1999
題意:
統計長度在 1 到 N 之間,元素大小都在 L 到 R 之間的單調不降序列的數量。
思路:
(雖然題目很簡潔但是公式的推導需要思考一下)
先推公式
設 M=R−L+1
長度為 i ,元素大小在 1...M 之間的單調不降序列的數量有 CM−1i+M−1 個
故答案為
∑Ni=1CM−1i+M−1
=(∑Ni=1CM−1i+M−1)+CMM−1
=(∑Ni=2CM−1i+M−1)+CMM+1−1
=(∑Ni=3CM−1i+M−1)+CMM+2−1
...
=CMN+M−1
然後Lucas定理直接上就行了
公式推導的解釋:假設序列長度為n,區間為[l,r],首先求出這一段的答案。
對于任意一個序列,将第i個數+i,那麼原來的問題就轉化為了n個在[l+1,r+n]區間以内的單調遞增的序列的個數。後者又相當于在[l+1...r+n]這r-l+n個數中取n個的方案數,即為C(r-l+n,n)=C(r-l+n,r-l)
是以,答案就相當于C(r-l+1,r-l)+C(r-l+2,r-l)+...+C(r-l+n,r-l)=C(r-l+n+1,r-l+1)-C(r-l,r-l)=C(r-l+n+1,n)-1。
由于模數不是很大,是以後面的答案是很容易得出的。如果知道lucas定理,會更簡單一點。
不預處理會逾時。
PS:lucas 定理用來計算組合數模素數。如果素數P可以先确定,則可以 O(P) 預處理,每次計算時間複雜度為 O(logpN) ,不預處理的時間複雜度O(mlogp)。
代碼:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e6+3;
ll fac[mod],inv[mod];
void Pretreatment(){//預處理
int i;
for(fac[0]=1,i=1;i<mod;i++)
fac[i]=fac[i-1]*i%mod;
for(inv[1]=1,i=2;i<mod;i++)
inv[i]=(mod-mod/i)*inv[mod%i]%mod;
for(inv[0]=1,i=1;i<mod;i++)
(inv[i]*=inv[i-1])%=mod;
}
ll C(int n,int m){
if(n<m) return 0;
if(n<mod && m<mod)
return fac[n] * inv[m] % mod * inv[n-m] % mod ;
return C(n/mod,m/mod) * C(n%mod,m%mod) % mod ;
}
int main(){
int t;
ll n,l,r;
scanf("%d",&t);
Pretreatment();
while(t--){
scanf("%d%d%d",&n,&l,&r);
int m=r-l+1;
printf("%d\n",(C(n+m, m)-1+mod)%mod);
}
return 0;
}