Hatena::Grouptopcoder

yuyarinのtopcoder記

TopCoder, Google Code JamPKU JudgeOnlineICPC などのアルゴリズム系プログラミングコンテストの参加や練習の記録を残していきます.

アルゴリズムやテーマで分類した目次はこちら

2010/03/02

SRM 463 RabbitNumbering

| 23:20

http://www.topcoder.com/stat?c=problem_statement&pm=10697&rd=14148

番号をつける条件が厳しい順,つまり M[i] が小さい順に考えていくため,まずソートする.

すると 0 番目の Rabbit はM[0] 通りの番号をつけられる,1 番目の Rabbit は M[1]-1 通りの番号をつけられる,n 番目の Rabbit は M[n]-n 通りの番号をつけられる.

M[n]-n が 0 以下であった場合は番号が振れなくなる.

32 bit だと integer overflow を起こすことに注意.long long を使う.

#include <cstdio>
#include <string>
#include <vector>
#include <iostream>
#include <sstream>

#define Forall(i,v)   for(int i=0;i<(int)v.size();++i)
#define Sort(c)     sort((c).begin(),(c).end())

class RabbitNumbering
{
public:

int theCount(vector <int> M)
{
	Sort(M);
	uint64_t r = 1;
	Forall(i,M)
	{
		if(M[i]<=i)
		{
			return 0;
		}
		r *= M[i]-i;
		r %= 1000000007ul;
	}
	return (int)r;
}
};