bzoj4403：序列統計

我好傻啊

題目

先來看看長度只能為\(n\)的情況

那么答案非常顯然是\(\binom{m+n-1}{n}\)

其中\(m=R-L+1\)

因為我們要構造一個非降序列，顯然可能一個數會被選擇多次，組合非常不好做，于是我們可以把每一個數的下標加上其對應的下標那么現在的值域范圍就變成了\([L+1,R+n]\)，從這個區間里選數的話，我們把選出來的數減去選好之后對應的下標，發現得到的數就來自于原來的\([L,R]\)，于是就變成了從\(R+n-L-1+1=n+m-1\)里選擇的\(n\)個數，就是\(\binom{n+m-1}{n}\)

也可以這樣理解，視為把\(n\)個小球放到\(m\)個盒子里，這樣的話多個小球可以放到同一個盒子里，就對應著一個數可以被選擇多次，盒子也可以是空著的，對應著一個數可以不被選擇，根據插板法，這樣的方案數就是\(\binom{n+m-1}{m-1}=\binom{n+m-1}{n}\)

現在的問題變成了求

\[\sum_{i=1}^{n}\binom{i+m-1}{m-1}\]

之后畫一下柿子就是\(\binom{n+m}{m}=\binom{n+m}{n}\)

之后上\(Lucas\)就好了

#include<iostream>
#include<cstring>
#include<cstdio>
#define LL long long
#define re register
#define maxn 1000005
const LL mod=1000003;
inline int read()
{char c=getchar();int x=0;while(c<'0'||c>'9') c=getchar();while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+c-48,c=getchar();return x;
}
LL fac[maxn],inv[maxn];
inline LL C(LL n,LL m)
{if(!m) return 1;if(!n) return 0;if(n==m) return 1;if(m>n) return 0;return fac[n]*inv[fac[m]*fac[n-m]%mod]%mod;
}
LL Lucas(LL n,LL m)
{if(!m) return 1;if(!n) return 0;if(n<mod&&m<mod) return C(n,m);return C(n%mod,m%mod)*Lucas(n/mod,m/mod)%mod;
}
int n,m,T,L,R;
int main()
{T=read();fac[0]=1;for(re int i=1;i<=mod;i++) fac[i]=fac[i-1]*i%mod;inv[1]=1;for(re int i=2;i<=mod;i++) inv[i]=(mod-mod/i)*inv[mod%i]%mod;while(T--){n=read(),L=read(),R=read();m=R-L+1;printf("%lld\n",(Lucas(n+m,m)-1+mod)%mod);}return 0;
}