HihoCoder - 1701 挑选子集(组合数，递推)

本文主要是介绍HihoCoder - 1701 挑选子集(组合数，递推)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

描述

给定N个整数A1, A2, … AN，小Hi希望从中选出M个整数，使得任意两个选出的整数的差都是K的倍数。

请你计算有多少种不同的选法。由于选法可能非常多，你只需要输出对1000000009取模的结果。

输入

第一行包含三个整数N、M和K。

第二行包含N个整数A1, A2, … AN。

对于30%的数据，2 ≤ M ≤ N ≤ 10

对于100%的数据，2 ≤ M ≤ N ≤ 100 1 ≤ K, Ai ≤ 100

输出

一个整数表示答案。

样例输入

5 3 2  
1 2 3 4 5

样例输出

1

思路

思路先用一个map保存一下，每个数对k取模的值，然后再对每一个余数个数大于等于m的求$C_n^m$，求组合数的时候用组合数的递推公式。

代码

#include <cstdio>
#include <cstring>
#include <cctype>
#include <stdlib.h>
#include <string>
#include <map>
#include <iostream>
#include <set>
#include <stack>
#include <cmath>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define mod 1000000009
typedef long long ll;
const int N=105+20;
map<int,int>mp;
int C[N][N];
void init()
{for(int i=0; i<=100; i++)C[i][0]=1;for(int i=1; i<=100; i++)for(int j=1; j<=i; j++){C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;}
}int main()
{int n,m,k,x;init();scanf("%d%d%d",&n,&m,&k);for(int i=1; i<=n; i++){scanf("%d",&x);mp[x%k]++;}int ans=0;map<int,int>::iterator it;for(it=mp.begin(); it!=mp.end(); it++){if((*it).second>=m){ans+=C[(*it).second][m];ans%=mod;}}cout<<ans<<endl;return 0;
}

这篇关于HihoCoder - 1701 挑选子集(组合数，递推)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---