网站部分网页乱码,爱营销电信版下载app最新版,营销课程培训哪个机构好,网站设计的创新点我好傻啊 题目 先来看看长度只能为\(n\)的情况 那么答案非常显然是\(\binom{mn-1}{n}\) 其中\(mR-L1\) 因为我们要构造一个非降序列#xff0c;显然可能一个数会被选择多次#xff0c;组合非常不好做#xff0c;于是我们可以把每一个数的下标加上其对应的下标那么现在的值域… 我好傻啊 题目 先来看看长度只能为\(n\)的情况 那么答案非常显然是\(\binom{mn-1}{n}\) 其中\(mR-L1\) 因为我们要构造一个非降序列显然可能一个数会被选择多次组合非常不好做于是我们可以把每一个数的下标加上其对应的下标那么现在的值域范围就变成了\([L1,Rn]\)从这个区间里选数的话我们把选出来的数减去选好之后对应的下标发现得到的数就来自于原来的\([L,R]\)于是就变成了从\(Rn-L-11nm-1\)里选择的\(n\)个数就是\(\binom{nm-1}{n}\) 也可以这样理解视为把\(n\)个小球放到\(m\)个盒子里这样的话多个小球可以放到同一个盒子里就对应着一个数可以被选择多次盒子也可以是空着的对应着一个数可以不被选择根据插板法这样的方案数就是\(\binom{nm-1}{m-1}\binom{nm-1}{n}\) 现在的问题变成了求 \[\sum_{i1}^{n}\binom{im-1}{m-1}\] 之后画一下柿子就是\(\binom{nm}{m}\binom{nm}{n}\) 之后上\(Lucas\)就好了 #includeiostream
#includecstring
#includecstdio
#define LL long long
#define re register
#define maxn 1000005
const LL mod1000003;
inline int read()
{char cgetchar();int x0;while(c0||c9) cgetchar();while(c0c9)x(x3)(x1)c-48,cgetchar();return x;
}
LL fac[maxn],inv[maxn];
inline LL C(LL n,LL m)
{if(!m) return 1;if(!n) return 0;if(nm) return 1;if(mn) 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(nmodmmod) return C(n,m);return C(n%mod,m%mod)*Lucas(n/mod,m/mod)%mod;
}
int n,m,T,L,R;
int main()
{Tread();fac[0]1;for(re int i1;imod;i) fac[i]fac[i-1]*i%mod;inv[1]1;for(re int i2;imod;i) inv[i](mod-mod/i)*inv[mod%i]%mod;while(T--){nread(),Lread(),Rread();mR-L1;printf(%lld\n,(Lucas(nm,m)-1mod)%mod);}return 0;
} 转载于:https://www.cnblogs.com/asuldb/p/10205701.html
