题解 P5160 【WD与循环】

· · 题解

题意:询问有多少个由非负整数构成的序列 (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));
    }
}