tg.BZOJ 4403序列统计
pj.BZOJ 4403序列统计
没啥用的题解
\(QWQ\)——无脑思考
- 首先要想怎么求单调不上升序列的个数，因为可能会有重复的数，所以不能直接用排列组合。
- 那这道题怎么打呀？
我不知道啊\(\dots\)
\((~:\)
- 因为原来是单调不下降序列，将第 \(i\) 位上的数加 \(i\) ，于是变成单调上升序列。于是 \(L\) 变成 \(L+1\) ,\(R\) 变成 \(R+n\) ,于是就要求出 $$\sum_{i=1}^{n}\binom {R-L+i}{R-L}$$
- 因为 $$\large\binom{n}{m}=\frac{n!}{m!(n-m)!}$$
- 所以 $$\large\binom{n}{m+1}=\frac{(n)!}{(m+1)!(n-m-1)!}$$
- 所以 $$\large\binom{n}{m}+\binom{n}{m+1}=\frac{n!}{m!(n-m)!}+\frac{n!}{(m+1)!(n-m-1)!}=\dfrac{(n+1)n!}{(m+1)m!(n-m)!}$$
- 最后得出 $$\large\dbinom{n}{m}+\dbinom{n}{m+1}=\binom{n+1}{m+1}$$
- 所以在第一个地方加上一个 \(\large\dbinom{R-L+1}{R-L+1}\) ,于是与第一个合并成为 \(\large\dbinom{R-L+2}{R-L+1}\) 。同理，最后合并成 \(\large\dbinom{R-L+n+1}{R-L+1}\) 。
- 所以 \(\large\dbinom{R-L+n+1}{R-L+1}\%P\) 就是每个输入的解。
容易死的地方
- \(\large n=0\) 时，要输出 \(0\) 。
- 记得加上模数，防止出来负数。
代码
#include<bits/stdc++.h>
#define ls (p<<1)
#define rs (p<<1|1)
#define endl '\n'
#define N (10000010)
#define int long long
using namespace std;
namespace IO
{
#define ll long long
const int MAX=1<<25;
char buf[MAX],*p1=buf,*p2=buf;
char obuf[MAX],*o=obuf;
#define gc()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
//template<typename T>
//inline T read()
inline int read()
{
int x=0;bool f=1;
char c=gc();
for(;c<48||c>57;c=gc())if(c=='-')f=0;
for(;c>=48&&c<=57;c=gc())x=(x<<3)+(x<<1)+(c^48);
return f?x:~x+1;
}
void print(ll x){if(x>9)print(x/10);*o++=(x%10)+'0';}
void pit(ll x){if(x<0)*o++='-',x=~x+1;print(x);}
void write(ll x,char end){pit(x);*o++=end;}
void flush(){fwrite(obuf,o-obuf,1,stdout);}
#undef ll
}
using IO::read;using IO::write;using IO::flush;
int n,m,t,P;
int x,y,k,L,R,tot,lon;
int len,prime[700010];//,phi[N];//线性筛欧拉函数
bitset<N>vis;
long long inv[N];//乘法逆元
inline int max(int x,int y){return x>y?x:y;}
inline int min(int x,int y){return x<y?x:y;}
inline void swap(int &x,int &y){int tmp=x;x=y;y=tmp;}
int e[N],siz[N];
long long qpow(long long x,int b,int P=P)
{
long long ans=1;
for(;b;b>>=1){if(b&1)ans=(ans*x)%P;x=(x*x)%P;}
return ans;
}//O(log(b))
int exgcd(int a,int b,int &x,int &y)
{
if(!b){x=1,y=0;return a;}
int d=exgcd(b,a%b,y,x);
y-=(a/b*x);
return d;
}//O(max(a,b))
int ola(int n)
{
int ans=n;
for(int i=2;i*i<=n;++i)
{
if(n%i==0)ans=ans/i*(i-1);
for(;n%i==0;n/=i);
}
if(n>1)ans=ans/n*(n-1);
return ans;
}//O(sqrt(n))
void eular(int n)//欧拉筛
{
//memset(vis,0,sizeof(vis));
//phi[1]=1;
for(int i(2);i<=n;++i)
{
if(!vis[i])
prime[++len]=i;//,phi[i]=(i-1);
for(int j(1);j<=len&&i*prime[j]<=n;++j)
{
vis[i*prime[j]]=1;
/*
if(!(i%prime[j]))
{phi[i*prime[j]]=(phi[i]*prime[j]);break;}
else phi[i*prime[j]]=(phi[i]*(prime[j]-1));
*/
}
}
}//O(n)
void niyuan1(int n)//乘法逆元
{
inv[1]=1;
for(int i(2);i<=n;++i)inv[i]=((P-P/i)*inv[P%i])%P;
}//O(n)
int inv_it(int a)//O(log(a))
{
int d(exgcd(a,P,x,y));
return (x%P+P)%P;
}
int C(int n,int m,int P=P)
{return (m>n)?0:(e[n]*qpow((e[m]*e[n-m])%P,P-2))%P;}
int lucas(int n,int m,int P=P)
{return (!m)?1:(C(n%P,m%P)*lucas(n/P,m/P))%P;}
void init()
{
P=(1e6)+3;e[1]=1;
for(int i(2);i<=(1e6)+4;++i)e[i]=(e[i-1]*i)%P;
}
signed main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
init();
for(t=read();t;--t)
{
n=read(),L=read(),R=read();
if(!n){write(0,'\n');continue;}
lon=R-L+1;
write((lucas(lon+n,lon)-1+P)%P,'\n');
}
flush();
return 0;
}