思路

任意两个序列都有至少一个相同的元素，但相同的元素不必在相同的位置。

保证每两个之间都要有相同的元素？

我们先考虑一下 \(n=k\times 2\) 的情况，此时如果你左边取一半,右边取一半,这时两边的元素才可能不一样。

那么当 \(n<k\times 2\) 时呢？此时你会发现不管怎么取,任意两条线段都会有重合的部分(即有相同的元素)。

那么此时就很简单了，总方案数就是 \(n\) 个里面取 \(k\) 个乘以 \(k\) 的排列方案,也就是:

\(\mathrm{C}_n^{k}\times k!\)

然后再是 \(n\ge k\times 2\) 的情况，从 \(n\) 个里面取出 \(k\) 个不能保证有同样的元素。

那么为什么不能我们自己来固定取一个数使其满足这个条件呢?那此时很简单，就当做从 \(n-1\) 个里面取 \(k-1\) 的方案数乘以k的排列数（为什么是 \(k\) 的排列数而不是 \(k-1\) 的排列数呢？因为我们固定的那个数也要参与排列啊！）也就是:

\(\mathrm{C}_{n-1}^{k-1}\times k!\)

那怎么去求呢?

首先，我们不能证明在对 \(10^9+7\) 取模的意义下,一个数乘以它在模 \(10^9+7\) 意义下的逆元与 \(1\) 同余,也就是我们在求 \(\mathrm{C}_{n-1}^{k-1}\) 时不需要用到除法运算了（取模运算和除法运算一起会出大问题）。

那事情就简单了，我们只需要预处理好每个数关于 \(10^9+7\) 的逆元，再将他们累乘求出他们阶乘的逆元，然后再算出每个数的阶乘，这样在下面使用的时候直接乘以逆元来当除法使用。

代码

2022-08-13 08:55:47 洛谷题解

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll h=1e9+7;
ll T,n,k,fac[1000006],inv[1000006];
void init(){
	fac[1]=fac[0]=1;
	for(int i=2;i<=1000000;i++){
		fac[i]=i*fac[i-1]%h;//每个数的阶乘 
	}
	inv[0]=inv[1]=1;
	for(int i=2;i<=1000000;i++){
		inv[i]=(h-h/i)*inv[h%i]%h;//每个数的逆元 
	}
	for(int i=2;i<=1000000;i++){
		inv[i]=inv[i]*inv[i-1]%h;//逆元的阶乘 
	}
	return;
}
int main(){
	init();
	cin>>T;
	while(T--){
		cin>>n>>k;
		if(n<=(k<<1)-1){
			printf("%lld\n",fac[k]*fac[n]%h*inv[k]%h*inv[n-k]%h);
		}
		else{
			printf("%lld\n",fac[k]*fac[n-1]%h*inv[k-1]%h*inv[n-k]%h);
	}
	return 0;
}