P1036 [NOIP2002 普及组] 选数

为什么这样写ans要除以k的阶乘

不太明白排列组合

#include<bits/stdc++.h>
#define ll long long 
#define maxn 25
#define maxn2 5001000
using namespace std;
int x[maxn],n,k,a[maxn],p[maxn2],use[maxn];ll ans;
void dfs(int pos){
	if(pos==k+1){
		int sum=0;
		for(int i=1;i<=k;i++)sum+=a[i];
		if(p[sum]==0)ans++;
		
		return;
	}
	for(int i=1;i<=n;i++){
		if(!use[i]){
			a[pos]=x[i];
			use[i]=1;
			dfs(pos+1);
			use[i]=0;
		}
	}
} 
int main(){
	cin>>n>>k;
	for(int i=1;i<=n;i++)cin>>x[i];
	//埃氏筛
	a[0]=a[1]=1;
	for(int i=2;i*i<=maxn2;i++)if(!p[i])for(int j=2*i;j<=maxn2;j+=i)p[j]=1;
	
	dfs(1);
	
	int we=1;
	for(int i=2;i<=k;i++)we*=i;
	
	cout<<ans/we;
	return 0;
}