問題
http://community.topcoder.com/stat?c=problem_statement&pm=10697&rd=14148
複数のうさぎが存在し、すべてのうさぎに番号をつけたい。
それぞれのうさぎは違う番号をつける。
各うさぎはつけて欲しい番号の最大数を持っており、１～その最大数までの
いずれかの数字をつける。
このとき、うさぎの番号の付け方の総数を求める。
解き方
普通に考えると計算量がオーバーしてしまう。
各うさぎのmaxnumberでソートし、小さい数から順番に見ていくことで
総数を簡単に数えることができる。
コード
class RabbitNumbering {
public: int theCount(vector<int> maxNumber) {
int MOD=1000000007;
int n=maxNumber.size();
int ret=1;
sort(all(maxNumber));
FORE(i,0,n){
ret=(ret*1LL*(maxNumber[i]-i))%MOD;
}
return ret;
}
};
public: int theCount(vector<int> maxNumber) {
int MOD=1000000007;
int n=maxNumber.size();
int ret=1;
sort(all(maxNumber));
FORE(i,0,n){
ret=(ret*1LL*(maxNumber[i]-i))%MOD;
}
return ret;
}
};