G 继续来数数

题目大意: 给定一个长度为 $nn$ 的非负整数数组 $aa$，保证 $aa$ 中元素至少有 $n\mathrm{-}1n-1$ 个数字互不相同。 求 $aa$ 的长度为 $kk$ 的不同子序列的方案数，输出答案取模$1e9+71e9+7$的结果。

解题思路:关注什么时候的子序列会重复，会发现在下图中，影响的子序列是不包含下标$33$至$55$的数且选择了一个重复的数

推广$::$设重复的数的下标为 ,总方案数易知为$C_n^{k}C^k\_n$,重复的方案为只选择一个重复的数,且不再选择$pos1pos1$至$pos2pos2$范围的数$(\mathrm{意}\mathrm{为}\mathrm{在}pos1\mathrm{与}pos2\mathrm{之}\mathrm{间}\mathrm{只}\mathrm{选}\mathrm{一}\mathrm{个}\mathrm{数})(意为在pos1与pos2之间只选一个数)$,方案数为$C_{n-(pos2-pos1+1)}^{k-1}C^\{k-1\}\_\{n-(pos2-pos1+1)\}$,所以答案为$C_n^k-C_{n-(pos2-pos1+1)}^{k-1}C^k\_n-C^\{k-1\}\_\{n-(pos2-pos1+1)\}$

$TipTip$:组合数$C_n^{m}C^m\_n$中当$m>nm>n$时，结果为$00$

参考代码:

#define LL long long
using namespace std;
const int M=1e5+7;
const LL Mod=1e9+7;
int T,n,k,x;
int a[M];
map<int,int> mp;
LL P[M],ipow[M];

LL C(int m,int n){
	if(m==0) return 1;
    if(n<m) return 0; //注意!!!
	return ((P[n]*ipow[m])%Mod*ipow[n-m])%Mod;
}


LL qpow(LL x,LL tim){
	LL ret=1,tmp=x;
	while(tim){
		if(tim&1){
			ret=ret*tmp%Mod;
		} 
		tmp=tmp*tmp%Mod;
		tim>>=1;
	}
	return ret;
}
int main(){
	ios::sync_with_stdio(false);
	cin>>T;
	P[0]=1;
	for(int i=1;i<=1e5+5;i++){
		P[i]=P[i-1]*i%Mod;
		//cout<<P[i]<<"\n";
	}
	ipow[0]=1;
	ipow[1]=1;
	for(int i=2;i<=1e5+5;i++){
		ipow[i]=qpow(P[i],Mod-2);
		//cout<<ipow[i]<<"\n";
	}
	while(T--){
		int pos1=0,pos2=0,f=0;
		cin>>n>>k;
		for(int i=1;i<=n;i++){
			cin>>a[i]; mp[a[i]]++;
			if(mp[a[i]]==2) {
				f=1;x=a[i];
			}
		}
		mp.clear();
		if(f==1){
			for(int i=1;i<=n;i++){
			    if(a[i]==x){
				     if(pos1) pos2=i;
				     else pos1=i;
			    }
		    }
		}
		if(f){
			cout<<(C(k,n)-C(k-1,n-pos2+pos1-1)+Mod)%Mod<<"\n";
		}
		else cout<<C(k,n)<<"\n";
	}
}