Throwing Dice(概率dp)

C - Throwing Dice

Time Limit:2000MS Memory Limit:32768KB 64bit IO Format:%lld & %llu

Description

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

3 9

1 7

24 24

15 76

24 143

23 81

7 38

Sample Output

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

//比赛没看懂题，这是一个简单概率dp，第一行是案例数 T ，然后 n ， m 是n个骰子掷出至少为 m 的概率。

dp[i][j]代表 i 个骰子，掷出 j 种数

dp[i][j]=SUM(dp[i-1][j-k]) (1<=k<=6)

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 using namespace std;
 5 #define LL long long
 6 
 7 int n,x;
 8 LL dp[30][155];
 9 
10 LL gcd(LL x,LL y)
11 {
12     return y?gcd(y,x%y):x;
13 }
14 
15 void Init()
16 {
17     for(int i=1;i<=6;i++)//一个骰子
18         dp[1][i]=1;
19     for(int i=2;i<25;i++)
20     {
21         for (int j=i;j<=6*i;j++)//i个骰子所有的点数
22         {
23             for (int k=1;k<=6;k++)
24             {
25                 if (j-k>=0)
26                 dp[i][j]+=dp[i-1][j-k];
27             }
28         }
29     }
30 }
31 
32 int main()
33 {
34     Init();
35     int T;
36     scanf("%d",&T);
37     for(int cas=1;cas<=T;cas++)
38     {
39         scanf("%d%d",&n,&x);
40         if(x>n*6)
41         {
42             printf("Case %d: 0
",cas);
43             continue;
44         }
45         if(x<=n)
46         {
47             printf("Case %d: 1
",cas);
48             continue;
49         }
50         LL up=0,down=1,g;
51         for(int i=x;i<=n*6;i++)
52             up+=dp[n][i];
53         for(int j=0;j<n;j++) down*=6;
54         g=gcd(up,down);
55         printf("Case %d: %lld/%lld
",cas,up/g,down/g);
56     }
57     return 0;
58 }

View Code