hihoCoder 1701 挑选子集

        题目链接： http://hihocoder.com/problemset/problem/1701

       基于桶排序的思想，这道题只用桶不用排序，因为任意两个数之差对k求余都等于0，所以只需要求pre[i]%k的值相等的有多少个，然后对其求组合方案数。

AC代码： 

#include <iostream>
#include <cstdio>
#include <cstring>
#define ll long long
#define mod 1000000009
using namespace std;
ll pre[1005];

ll c(ll n,ll m){
  ll sum1 = 1;
  for(long long i = 1 ; i <= m; i ++){
        sum1 = sum1 * (n + 1 - i) / i;
    }
    return sum1 % mod;  
}

int main()
{
  ll n,m,k,ans;
  scanf("%lld%lld%lld",&n,&m,&k);
  memset(pre,0,sizeof(pre));
  for(ll i=0;i<n;i++){
    scanf("%lld",&ans);
    pre[ans % k]++;
  }
  ll sum = 0;
  for(ll i=0;i<k;i++){
    sum += c(pre[i],m);
    sum %= mod;
  }
  cout<<sum<<endl;
  return 0;
}