浩替

注意到这是一个非严格单增序列，这很不好

如果它是严格单增的话，就相当于一个普通的组合数$\sum_{i=1}^{m} C_{t-s+1}^{i}$

那么考虑转化，将 $A_1$ 加 $1$ ，$A_2$ 加 $2$ ，这样，它就能变成严格单增，然后他的上下界就变成了 $s+1$ 和 $t+n$

共 $(t+n)-(s+1)+1 = t-s+n$ 个坑位

所以就有柿子：

$$\sum_{i=1}^{m} C_{t-s+i}^{i}$$

但是不能遍历 $m$ ，考虑化简

有式子 $C_{n}^{m} = C_{n-1}^{m} + C_{n-1}^{m-1}$

带入得

$$\sum_{i=1}^{m} C_{t-s+i}^{i} = \sum_{i=1}^{m} (C_{t-s+i+1}^{i}-C_{t-s+i}^{i-1}) $$

注意到临项之间可以抵消，因此

$$原式 = C_{t-s+m+1}^{m} - C_{t-s+1}^{0} = C_{t-s+m+1}^{m} - 1 $$

于是你就推出了这一个伟大的式子！！

$$C_{t-s+m+1}^{m} - 1$$

可是注意到 $s,t,m$ 特别大，但是模数特别小

直接上Lucas模板！

#include<iostream>
#include<cstdio>

using namespace std;

const long long mod=1000003;

inline long long ksm(long long a,long long b){
	long long res=1;
	while (b){
		if (b&1) res=res*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return res;
}
long long fac[1000010],inv[1000010];
inline void init(long long N){
	fac[0]=inv[0]=1;
	for (int i=1;i<=N;i++){
		fac[i]=fac[i-1]*i%mod;
	}
	inv[N]=ksm(fac[N],mod-2);
	for (int i=N-1;i>=1;i--){
		inv[i]=inv[i+1]*(i+1)%mod; 
	}
	return;
}
long long C(long long n,long long 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;
}

long long T,m,s,t;

int main(){
	init(1000002);
	scanf("%lld",&T);
	while (T--){
		scanf("%lld%lld%lld",&m,&s,&t);
		printf("%lld\n",(C(t-s+m+1,m)-1+mod)%mod);
	}
	return 0;
} 

到底是谁造的数据一堆0-1，减法取模不加mod愉快的死了100->30。

这个题真就纯数学题，不会计算机也没关系的说。

题面

给定整数 $m,s,t\in[1,10^9],s\le t$（就是喜欢写区间），构造长度为 $n$ 的整数序列 $A$，使得其满足如下条件。

• $n\in[1,m]$
• $\forall i \in Z,i\in [1,n]$ 满足 $A_i\in[s,t]$
• $\forall i \in Z,i\in [1,n)$ 满足 $A_i\le A_{i+1}$

求可以构造多少个不同的序列 $A$，输出方案数对 1000003 取模的结果。

思路

考虑化简问题（MO和OI似乎都很吃随机思考能力，但方向又不太一样），序列长度不同太让人抓狂了，把原问题化简为子状态，即确定序列长度 $len$，往里面填 $v$ 个数的方案数，容易发现这个题的 $v$ 恒等于 $t-s+1$。

这就很 dp 了，把上面随机思考的过程翻译一下：设状态 $f[i][j]$ 表示长度为 $i$ 的序列可以填 $j$ 个区分大小的数，最终合法方案数。

最终答案为

$$\sum_{i=1}^{m}f[i][v]$$

考虑状态转移，这时候我的想法是1e9范围，大概是矩阵加速递推，所以只考虑一行，看看是否存在递推关系,结果这样似乎误打误撞的缩小了问题规模。首先一定有 $f[1][1]=1$。

根据我这个不会做数学题的彩笔多年经验，哎我不会推式子我还不会找规律了嘛。

前面发现要求的和中 $v$ 恒等，所以我就开始画 $f[i][2],f[i][3]$ 的所有情况。

$f[1][2]$:0,1;

$f[2][2]$:00,01|11;

$f[3][2]$:000,001,011|111;

不是很好发现规律，每个较于上一个+1这种显然不普遍。但是$f[i][j]$ 显然包含 $f[i-1][j]$ 的部分

$f[1][3]$:0,1,2;

$f[2][3]$:00,01,02|11,12,22;

$f[3][3]$:000,001,002,011,012,022|111,112,122,222;

这时候你发现右半部分有点眼熟，$f[2][3]$ 的右半部分和 $f[2][2]$ 本质相同，$f[3][3]$ 的右半部分和 $f[3][2]$ 本质相同。

所以得到递推式 $f[i][j]=f[i-1][j]+f[i][j-1]$，这毕竟是找规律发现的，我自己的解释有点只可意会不可言传，感性理解就好了。

其实如果你学过一点组合看到这个式子就该气笑了，这就是大名鼎鼎的杨辉三角（笛卡尔三角形）递推式，二项式定理递推式，组合数递推式。当然这个杨辉三角横过来了，还错了一位。画个图讲吧。

时至今日，我们似乎得放弃矩阵加速的解法了。

这就是由这个递推式所求出的矩形。对于 $m=3,v=3(t-s+1=3)$ 所求的方案数是蓝色圈中的数相加，也就是 $f[1][3]+f[2][3]+f[3][3]=C_3^1+C_4^2+C_5^3$.

进而可以推导得答案为

$$\sum_{i=1}^{m}C_{v-1+i}^{i}$$

我有不是数学佬，怎么可能会算这玩意，于是继续找规律，开始暴力计算。蓝圈中的和为 19，诶诶，10 下面的数是 20，莫非...？

还真是，看第二行 2+3+4+5 = 14。5下面是15。第三行3+6+10+15=34，下面是35。

这一行的和正好等于下面的数-1.

不管了直接用吧。由于这个矩阵是把杨辉三角扭了一下，所以推起来还不太容易，最终得到

$$\sum_{i=1}^{m}C_{v-1+i}^{i}=C_{v+m}^{v}-1$$

由于 $v,m$ 的值域都是 $10^9$，所以直接按组合数公式计算肯定会超时，所以要使用 Lucas 定理。

设 $Lucas(x,y)=\binom{x}{y}\bmod p(p\in P)$

则 $Lucas(x,y)=Lucas(\lfloor x/p\rfloor,\lfloor y/p\rfloor )\binom{x\bmod p}{y\bmod p}$

后记

这两天发现了一个这样的公式。

$$\sum_{i=0}^{n}C_{a+i}^{a}=C_{a+n+1}^{a+1}$$

即朱世杰恒等式。

所以给出上面我猜的式子的证明：

$$\begin{aligned} \sum_{i=1}^{m}C_{v-1+i}^{i} &= \sum_{i=0}^{m}C_{v-1+i}^{i}-1 \\ &= \sum_{i=0}^{m}C_{v-1+i}^{(v-1+i-i)}-1&=\sum_{i=0}^{m}C_{v-1+i}^{v-1}-1\\ 根据朱世杰恒等式，设v-1=a\\ &=C_{a+m+1}^{a+1}-1\\ &=C_{v+m}^{v}-1 \end{aligned}$$

第一步显然，第二行根据组合数对称性，第三步套用朱世杰恒等式。

哇这个笔记写的太爽了。

Lucas 写炸了彻底怒了

这个题 $a,b$ 没啥用，他能取的数字个数为 $b-a+1$ ，我们们设函数 $f_{x,y}$ 的值为能取到的数字个数为 $x$ 个，这个 $S$ 的长度为 $y$ 的情况数，我们就有式子：

$$Ans=\sum_{i=1}^n f_{b-a+1,i}$$

然后我们想怎么求单个的 $f_{x,y}$。

列一下情况 $f_{1,1}=1$ 情况为 1， $f_{1,2}=1$ 情况为 11 ， $f_{2,1}=2$ 情况为 1,2 ， $f_{2,2}=1$ 情况为 11,12,22 ， $f_{3,1}=3$ 情况为 1,2,3 ， $f_{3,2}=6$ 情况为 11,12,13,22,23,33

我们可以把每一个 $f_{x,y}$ 的所有情况看成 $f_{x-1,y}$ 的所有情况和 $f_{x,y-1}$ 的所有情况后面加上一个数字 $y$ ，然后就有 $f_{x,y}=f_{x-1,y}+f_{x,y-1}$ 我们就可把它抽象成一个杨辉三角，那么 $f_{x,y}=C_{x+y-1}^{y}$

所以

$$Ans=\sum_{i=1}^nC_{b-a+i}^{i}=C_{b-a+n+1}^{n}-1$$

然后 Lucas就可以了

Lucas定理

Lucas 定理是一种求组合数是取模数 $p$ 为质数情况下的快速求法，Lucas 定理内容：

$$\left( \begin{array}{c} n \\ m \end{array} \right)\equiv \left( \begin{array}{c} n \mod p \\m \mod p\end{array} \right)\left( \begin{array}{c} \lfloor\frac{n}{p}\rfloor \\ \lfloor\frac{m}{p}\rfloor \end{array} \right)\mod p $$

当 $n<k$ 时，$\left( \begin{array}{c} n \\ m \end{array} \right)$ 规定为 $0$

首先，a, b 就是来搞笑的，直接向左平移 a-1，相当于选取不超过 b-a+1 的正整数。

令 m=b-a+1

从 1, 2, ……, m 中选取 k （1 ≤ k ≤ n）个数，每个数可以不选，也可以重复选取，构成一个有序序列。

有多少种选取方案，就有多少个序列。因为序列是有序的，选出来数之后，排个序，自然对应一个有序序列。

设选取了 $x_1$ 个 1，$x_2$ 个 2，……，$x_m$ 个 m，则：

$x_1 + x_2 + …… + x_m = k$

相当于求不同解的个数。

相当于把 k 个相同的小球放到 m 个不同的盒子里，盒子可以为空，求放法总数。

经典的组合问题。

先在每个盒子里放一个小球，然后用隔板法。

C(k+m-1,m-1)

而 k 的取值范围是 1 ≤ k ≤ n

所以 ans = $\sum\limits_{k=1}^n C(k+m-1,m-1)$

化简

利用卢卡斯定理