隔板法
枚举当前序列的长度k:$a_1,a_2,\cdots,a_k$
然后用差分映射称新序列:$x_1,x_2,\cdots,x_k$
则有 $x_1+x_2+\cdots+x_k \le R - L$,其中 $x_i \ge 0$
令 $y_i = x_i + 1$,则有$y_1+y_2+\cdots+y_k \le R - L + k$,其中 $y_i > 0$
于是我们就可以用隔板法了hh
最终的方案数为 $C_{R - L + k} ^ k$
因为这里是不等式,所以所有小球不一定都要用完,我们额外加一个板子放到最后,当作一个虚无的数
总的方案数表达式如下:
$$ \begin{align} \sum_{k=1}^N C_{R-L+k}^k &= \sum_{k=1}^N C_{m+k}^k \\\ &= C_{m+1}^1 + C_{m+2}^2 + \cdots + C_{m+N}^N \\\ &= C_{m+1}^m + C_{m+2}^m + \cdots + C_{m+N}^m \\\ &= C_{m+1}^{m+1} + C_{m+1}^m + C_{m+2}^m + \cdots + C_{m+N}^m - C_{m+1}^{m+1} \\\ &= C_{m+2}^{m+1} + C_{m+2}^m + \cdots + C_{m+N}^m - C_{m+1}^{m+1} \\\ &= \cdots \\\ &= C_{m+N+1}^{m+1} - 1 \\\ &= C_{R-L+N+1}^{R-L+1} - 1 \end{align} $$
#include <iostream>
using namespace std;
typedef long long LL;
const int p = 1e6 + 3;
int qmi(int a, int b) {
int res = 1;
while (b) {
if (b & 1) res = (LL) res * a % p;
a = (LL) a * a % p;
b >>= 1;
}
return res;
}
int C(int a, int b) {
int up = 1, down = 1;
for (int i = a, j = 1; j <= b; ++ j, -- i) {
up = (LL) up * i % p;
down = (LL) down * j % p;
}
return (LL) up * qmi(down, p - 2) % p; //逆元
}
int Lucas(int a, int b) {
if (a < p && b < p) return C(a, b);
return (LL)C(a % p, b % p) * Lucas(a / p, b / p) % p;
}
int main() {
int T;
cin >> T;
while (T -- ) {
int n, l, r;
cin >> n >> l >> r;
cout << (Lucas(r - l + n + 1, r - l + 1) - 1 + p) % p << endl;
}
return 0;
}
大佬,为啥这里的求组合数方法不是像基础课组合数3里那样边循环边求逆元,而是最后统一到最后再求逆元啊?
难道 $ inv(a/b) \equiv inv(a)*inv(b) $ ?