自动搬运

查看原文

来自洛谷，原作者为

	Fading AFO

搬运于2025-08-24 22:07:46，当前版本为作者最后更新于2018-12-30 22:00:26，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

题意:询问有多少个由非负整数构成的序列 $(a_1,a_2,... ,a_n)$

满足

$$a_1 + a_2 + ... + a_n \leq m$$

如果是 $a_1 + a_2 + ... + a_n = m$，很简单，直接上隔板法，答案就是 $C^{n-1}_{n+m-1}$

那么如果是 $\leq$ 呢？直接求和就好了。

$$ans=\sum_{i=0}^{n+m-1}C^{m-1}_{i}$$

我看看数据范围就放弃了暴力。但是我打了一个杨辉三角的表就发现：

$$\sum_{i=0}^{n}C^{m}_{i}=C_{n+1}^{m+1}$$

也就是

$$\sum_{i=1}^{n+m}C^{m-1}_{n+m-i}=C_{n+m}^{m}$$

所以和lucas定理模板题就是双倍经验了

这是为什么呢？

我们考虑数学归纳法。

证明：

$$\sum_{i=0}^{n}C^{m}_{i}=C_{n+1}^{m+1}(n,m\geq0)$$

若 $n=0$，分类讨论一下就知道成立了。什么鬼证明

假设 $n=k$ 时结论成立，即

$$\sum_{i=0}^{k}C^{m}_{i}=C_{k+1}^{m+1}$$ $$∴(\sum_{i=0}^{k}C^{m}_{i})+C_{k+1}^{m}=C_{k+1}^{m+1}+C_{k+1}^{m} $$

根据组合数的性质（杨辉三角的性质）

$$C_{n-1}^{m-1}+C_{n-1}^{m}=C_{n}^{m}$$ $$∴\sum_{i=0}^{k+1}C^{m}_{i}=(\sum_{i=0}^{k}C^{m}_{i})+C_{k+1}^{m}=C_{k+1}^{m+1}+C_{k+1}^{m}=C_{k+2}^{m+1} $$

即对于 $n=k+1$ 时结论也成立

综上所述，对于 $(n,m\geq0)$ 时结论成立。

---

这题就变成一道组合数裸题了。

题目出的还是挺不错的。套一下 Lucas 就好了！

个人感觉是蓝~紫题吧，评成黑题的话就有点厉害了。

代码：

#include<bits/stdc++.h>
#define LL long long
using namespace std;
LL fa[19491003],T,n,m,pp;
LL fast_pow(LL a,LL b,LL p){    
    LL t=1;a%=p;
    while (b>0){
        if (b%2) t=t*a%p;
        b/=2;a=(a*a)%p;
    }
    return t;
}
LL un(LL a,LL p){
    return fast_pow(a,p-2,p); 
}
void _init(LL p){
    fa[0]=1;
    for (int i=1;i<=p;i++){
        fa[i]=fa[i-1]*(i%p);fa[i]%=p;
    }
}
LL C(LL n,LL m,LL p){ 
    if (n<m) return 0;
    return fa[n]*un(fa[n-m],p)%p*un(fa[m],p)%p;
}
LL fast_C(LL n,LL m,LL p){
    if (n<m) return 0;
    if (!n) return 1;
    return fast_C(n/p,m/p,p)%p*C(n%p,m%p,p)%p;
}
int main(){
    scanf("%lld",&T);
    _init(19491001);
    while (T--){
        scanf("%lld%lld",&n,&m);
        printf("%lld\n",fast_C(n+m,m,19491001));
    }
}