UVa 10759 Dice Throwing：概率DP

UVa 10759 Dice Throwing：概率DP2014-07-29 csdn博客 synapse710759 - Dice Throwing

Time limit: 3.000 seconds

http://uva.onlinejudge.org/index.php？option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1700

n common cubic dice are thrown. What is the probability that the sum of all thrown dice is at least x？

Input

The input file contains several test cases. Each test case consists two integers n （1<=n<=24） and x（0<=x<150）. The meanings of n and x are given in the problem statement. Input is terminated by a case where n=0 and x=0. This case should not be processed.

Output

For each line of input produce one line of output giving the requested probability as a proper fraction in lowest terms in the format shown in the sample output. All numbers appearing in output are representable in unsigned 64-bit integers. The last line of input contains two zeros and it should not be processed.

Sample Input Output for Sample Input

20/27

从下往上慢慢加~

f[i + 1][j + k] += f[i][j];

完整代码：

/*0.015s*/#include<cstdio>typedef unsigned long long ull;ull f[25][150];ull gcd（ull a, ull b）{return b ？ gcd（b, a % b） : a;}int main（）{int i, j, k, n, x;ull ans, b, g;for （i = 1; i <= 6; ++i）f[1][i] = 1;for （i = 1; i < 25; ++i）for （j = i; j <= 6 * i; ++j）for （k = 1; k <= 6; ++k）f[i + 1][j + k] += f[i][j];while （scanf（"%d%d", &n, &x）, n）{if （x > 6 * n）{puts（"0"）;continue;}else if （x <= n）{puts（"1"）;continue;}ans = 0, b = 1;for （i = x; i <= 6 * n; ++i） ans += f[n][i];for （i = 0; i < n; ++i） b *= 6;g = gcd（ans, b）;printf（"%llu/%llu
", ans / g, b / g）;}}