P5135 painting 题解

· · 题解

题目传送门

前置知识

众所周知，组合有两种：非重组合和可重组合。非重组合的公式是 C^m_n，可重组合的是 C^m_{n+m-1}。既然已经在题目标签里看到了“组合数学”（？），我们就可以想办法将这两种组合与这道题结合在一起。

题目分析

我们通过 opt 的值来分类讨论。

opt 的值为 1

因为 Wolfycz 想要的是 m 个不相等的行数，我们可以把连线忽略不管，因为我们只要得到了 m 个不相等的行数，将它们排序一下就是严格下降的连线了。因此可以发现，这不就是求非重组合吗？的确，只要用一下上文所说的非重组合的公式即可（刚刚说的排序其实是题外话，因为我们并不需要求出一个组合，只是求组合数而已）。

opt 的值为 0

和上面那种情况差不多，我们看一下就可以发现，随便弄出 m 个可以相等的行数，然后将它们排一下序，它们就肯定会变成不上升的连线。因此这就是可重组合。和上面的情况一样，用可重组合的公式（C^m_{n+m-1}）即可。

代码实现

（下面用 Lucas 定理其实是大材小用，把 Lucas 部分删掉直接用普通的 C 算组合数应该也可以）

#include<cstdio>
#define int long long
using namespace std;
const int maxn=1e6;
const int mod=1e9+7;
int t,n,m,opt,inv[maxn+1];
inline int pow(int a,int b,int p){
    int res=1;
    while(b){
        if(b&1) res=res*a%p;
        b>>=1,a=a*a%p;
    }
    return res;
}
inline int C(int n,int m,int p){
    if(m>n) return 0;
    int x=1,y=1;
    for(int i=1;i<=m;++i) x=x*(n-i+1)%p,y=y*i%p;
    return x*pow(y,p-2,p)%p;//用逆元求组合数
}
inline int Lucas(int n,int m,int p){
    if(m==0) return 1;
    return C(n%p,m%p,p)*Lucas(n/p,m/p,p)%p;
}
signed main(){
    scanf("%lld",&t);
    while(t--){
        scanf("%lld%lld%lld",&n,&m,&opt);
        if(opt==1) printf("%lld\n",Lucas(n,m,mod));
        else printf("%lld\n",Lucas(n+m-1,m,mod));
    }
    return 0;
}

写在最后

希望这篇题解能让大家有所收获，有所收获的同时不要忘了留下一个免费的赞（