JOI2006模擬試験2 問題5＠C++(25)

よくある数学の組合せ論の知識かと思って解いたらミスった。そりゃ、組合せ論的な規模の数って言ったら多倍長だもんなあ。

つーかSTLに多倍長ってないのかよ使えねー！Javaならあるのに！Pythonなんか標準で多倍長だし！

多倍長ライブラリのバグで何度も爆発(wrongを出す)した。orz

#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;

typedef unsigned long long ullong;
typedef unsigned int uint;

//minimalist mutable unsigned decimal big number;
class decimal_big
{
private:
	//100000 separated digits value;
	vector<uint> digits;
public:
	void div(uint target) {
		ullong ull_target=target;
		ullong carry=0;
		for(vector<uint>::reverse_iterator i=digits.rbegin();i!=digits.rend();++i) {
			ulong ull_current=*i;
			ull_current=ull_current+carry;
			*i=(uint)(ull_current/ull_target);
			carry=(ull_current%ull_target)*100000;
		}
		while(!digits.empty() && digits.back()==0) {
			digits.pop_back();
		}
	}
	void mul(uint target) {
		ullong ull_target=target;
		uint carry=0;
		for(vector<uint>::iterator i=digits.begin();i!=digits.end();++i) {
			ullong ull_current=*i;
			ull_current=ull_current*ull_target+carry;
			*i=(uint)(ull_current%100000);
			carry=(uint)(ull_current/100000);
		}
		if(carry>0) {
			digits.push_back(carry);
		}
		while(!digits.empty() && digits.back()==0) {
			digits.pop_back();
		}
	}
	void print() {
		while(!digits.empty() && digits.back()==0) {
			digits.pop_back();
		}
		if(digits.empty()) {
			printf("0");
			return;
		}
		for(vector<uint>::reverse_iterator i=digits.rbegin();i!=digits.rend();++i) {
			if(i==digits.rbegin()) {
				printf("%u",*i);
			} else {
				printf("%05u",*i);
			}
		}
	}
	void set_single(uint single_value) {
		digits.clear();
		digits.push_back(single_value);
	}
	decimal_big() {
		
	}
};

void long_combination(int all,int select,decimal_big& dst)
{
	if(select<0 || select>all) {
		dst.set_single(0);
		return;
	}
	dst.set_single(1);
	for(int i=0;i<select;i++) {
		dst.mul(all-i);
		dst.div(1+i);
	}
}

int main(int argc,char* argv[])
{
	int n,m,r;
	scanf("%d %d %d\n",&n,&m,&r);
	int realr=r-n*m;
	int separators=n-1;
	decimal_big pattern;
	long_combination(realr+separators,separators,pattern);
	pattern.print();
	printf("\n");
	return 0;
}