Cut the Cake

2
3 3
3 4

1/3
4/27

题意：M个小伙伴分蛋糕，有N个草莓随机分布在蛋糕上，你去把蛋糕平均切，并优先选择一块，问你能拿到所有草莓的概率。

思路:以最外面的一个草莓为第一刀为切的位置，这样一共有N种开刀位置，然后剩下N-1个草莓，每个的概率为1/M.如此以来概率为N / M ^ (N - 1); 要使用高精度，并且化简输出。

代码：

#include <stdio.h>
#include <string.h>
#include <iostream>

using namespace std;
const int N = 1005;

struct bign {
    int len, sex;
    int s[N];

    bign() {
	this -> len = 1;
	this -> sex = 0;
	memset(s, 0, sizeof(s));
    }


    bign operator = (const char *number) {
	int begin = 0;
	len = 0;
	sex = 1;
	if (number[begin] == ‘-‘) {
	    sex = -1;
	    begin++;
	}
	else if (number[begin] == ‘+‘)
	    begin++;

	for (int j = begin; number[j]; j++)
	    s[len++] = number[j] - ‘0‘;
	return *this;
    }
    bign operator = (int number) {
	char string[N];
	sprintf(string, "%d", number);
	*this = string;
	return *this;
    }
    bign (int number) {*this = number;}
    bign (const char* number) {*this = number;}

    bign change(bign cur) {
	bign now;
	now = cur;
	for (int i = 0; i < cur.len; i++)
	    now.s[i] = cur.s[cur.len - i - 1];
	return now;
    }

    void delZore() {	// 删除前导0.
	bign now = change(*this);
	while (now.s[now.len - 1] == 0 && now.len > 1) {
	    now.len--;
	}
	*this = change(now);
    }

    void put() {    // 输出数值。
	delZore();
	if (sex < 0 && (len != 1 || s[0] != 0))
	    cout << "-";
	for (int i = 0; i < len; i++)
	    cout << s[i];
    }

    bign operator * (const bign &cur){  
	bign sum, a, b;
	sum.len = 0; 
	a = a.change(*this);
	b = b.change(cur);

	for (int i = 0; i < a.len; i++){  
	    int g = 0;  

	    for (int j = 0; j < b.len; j++){  
		int x = a.s[i] * b.s[j] + g + sum.s[i + j];  
		sum.s[i + j] = x % 10;  
		g = x / 10;  
	    }  
	    sum.len = i + b.len;  

	    while (g){  
		sum.s[sum.len++] = g % 10;  
		g = g / 10;  
	    }  
	}  
	return sum.change(sum);  
    }  

    bign operator / (int k) {  // 高精度求商低精度。
	bign sum;  
	sum.len = 0;  
	int num = 0;  
	for (int i = 0; i < len; i++) {  
	    num = num * 10 + s[i];  
	    sum.s[sum.len++] = num / k;  
	    num = num % k;  
	}  
	return sum;  
    }

    int operator % (int k){  
	int sum = 0;  
	for (int i = 0; i < len; i++){  
	    sum = sum * 10 + s[i];  
	    sum = sum % k;  
	}  
	return sum;  
    } 

    bool operator < (const bign& b) const {
	if (len != b.len)
	    return len < b.len;
	for (int i = 0; i < len; i++)
	    if (s[i] != b.s[i])
		return s[i] < b.s[i];
	return false;
    }
    bool operator > (const bign& b) const { return b < *this; }
    bool operator <= (const bign& b) const { return !(b < *this); }
    bool operator >= (const bign& b) const { return !(*this < b); }
    bool operator != (const bign& b) const { return b < *this || *this < b;}
    bool operator == (const bign& b) const { return !(b != *this); }
};

int t, n, M;
bign zero = 0;

int main () {
    scanf("%d", &t);
    while (t--) {
	scanf("%d%d", &M, &n);
	bign m = M;
	bign ans = 1;
	for (int i = 1; i < n; i++)
	    ans = ans * m;
	for (int i = n; i >= 2; i--) {
	    if (n % i == 0 && ans % i == 0) {
		n /= i;
		ans = ans / i;
	    }
	    if (n == 1) break;
	}
	printf("%d/", n);
	ans.put();
	printf("\n");
    }
    return 0;
}

HDU 4762 Cut the Cake(概率+推理+高精度),布布扣,bubuko.com

HDU 4762 Cut the Cake(概率+推理+高精度)

原文：http://blog.csdn.net/accelerator_/article/details/20863155