题目链接: 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;
}