lightoj1064_简单dp

http://lightoj.com/volume_showproblem.php?problem=1064

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

Input

Input starts with an integer T (≤ 200), denoting the number of test cases.

Each test case contains two integers n (1 ≤ n < 25) and x (0 ≤ x < 150). The meanings of n and x are given in the problem statement.

Output

For each case, output the case number and the probability in 'p/q' form where p and q are relatively prime. If q equals 1 then print p only.

Sample Input

Output for Sample Input

3 9

1 7

24 24

15 76

24 143

23 81

7 38

Case 1: 20/27

Case 2: 0

Case 3: 1

Case 4: 11703055/78364164096

Case 5: 25/4738381338321616896

Case 6: 1/2

Case 7: 55/46656

 1 #include <algorithm>
 2 #include <iostream>
 3 #include <cstring>
 4 #include <cstdlib>
 5 #include <cstdio>
 6 #include <vector>
 7 #include <ctime>
 8 #include <queue>
 9 #include <list>
10 #include <set>
11 #include <map>
12 using namespace std;
13 #define INF 0x3f3f3f3f
14 typedef long long LL;
15 
16 LL dp[30][150];
17 int main()
18 {
19     int t, n, x;
20     scanf("%d", &t);
21     for(int ca = 1; ca <= t; ca++)
22     {
23         scanf("%d %d", &n, &x);
24         memset(dp, 0, sizeof(dp));
25         for(int i = 1; i <= 6; i++)
26             dp[1][i] = 1;
27         LL sum = 6;
28         for(int i = 2; i <= n; i++)
29         {
30             sum *= 6;
31             for(int j = i*6; j > 0; j--)
32             {
33                 for(int k = 1; k <= 6; k++)
34                 {
35                     if(j-k > 0)
36                         dp[i][j] += dp[i-1][j-k];
37                 }            
38             }
39         }
40         LL res = 0;
41         for(int i = x; i <= n * 6; i++)
42             res += dp[n][i];
43         printf("Case %d: ", ca);
44         if(res == 0){
45             printf("0
");
46             continue;
47         }
48         if(sum == res)
49         {
50             printf("1
");
51             continue;
52         }
53         LL te = __gcd(res, sum);
54         printf("%lld/%lld
", res/te, sum/te);
55     }
56     return 0;
57 }