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
7
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/4665
题解:dp[ i ][ j ]表示 i 个骰子掷出和为 j 的方案数。
所以,dp[ i ][ j ]=dp[ i ][ j ]+dp[ i - 1 ][ j - k ](1<=k<j)
1 #define INF 1e8
2 #include<cstdio>
3 #include<cstring>
4 #include<iostream>
5 #include<algorithm>
6 using namespace std;
7 typedef long long ll;
8
9 int n,x;
10 ll sum;
11 ll dp[25][150];
12
13 ll gcd(ll a,ll b){
14 return b==0?a:gcd(b,a%b);
15 }
16
17 void solve(){
18 sum=1;
19 memset(dp,0,sizeof(dp));
20 dp[0][0]=1;
21 for(int i=1;i<=n;i++){
22 sum=sum*6;
23 for(int j=1;j<=i*6;j++)
24 for(int k=1;k<=6;k++)
25 if(j>=k) dp[i][j]=dp[i][j]+dp[i-1][j-k]; //因为dp[0][0]=1,所以j一定要大于等于k,否则不能更新dp[i][j]的值
26 }
27 }
28
29 int main()
30 { int kase;
31 cin>>kase;
32 for(int t=1;t<=kase;t++){
33 cin>>n>>x;
34 solve();
35 ll ans=0;
36 for(int i=x;i<=n*6;i++) ans+=dp[n][i];
37 ll temp=gcd(sum,ans);
38 if(ans==0) printf("Case %d: 0\n",t);
39 else if(ans==sum) printf("Case %d: 1\n",t);
40 else printf("Case %d: %lld/%lld\n",t,ans/temp,sum/temp);
41 }
42 }
转载于:https://www.cnblogs.com/zgglj-com/p/7341045.html