自动搬运

查看原文

来自洛谷，原作者为

	xiaomuyun 你的黑粉比我多，所以你比我强

搬运于2025-08-24 22:07:30，当前版本为作者最后更新于2022-07-06 20:40:45，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题目传送门

前置知识

众所周知，组合有两种：非重组合和可重组合。非重组合的公式是 $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;
}

写在最后

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