小易参加了一个骰子游戏,这个游戏需要同时投掷n个骰子,每个骰子都是一个印有数字1~6的均匀正方体。
小易同时投掷出这n个骰子,如果这n个骰子向上面的数字之和大于等于x,小易就会获得游戏奖励。
小易想让你帮他算算他获得奖励的概率有多大。
输入包括两个正整数n和x(1 ≤ n < 25, 1 ≤ x < 150),分别表示骰子的个数和可以获得奖励的最小数字和。
输出小易可以获得奖励的概率。 如果概率为1,输出1,如果概率为0,输出0,其他以最简分数(x/y)的形式输出。
3 9
20/27
package main import ( "fmt" ) func gcd(a, b int) int { for b > 0 { a, b = b, a % b } return a } func f(n, x int) (t, m int) { if x <= n { t = 1 m = 1 return } if x > n * 6{ t = 0 m = 1 return } s := make([][]int, n) for i:=0; i<n; i++ { s[i] = make([]int, 6*n) for j:=0; j < 6*n; j++ { s[i][j] = 0 } } for i:=0; i<n; i++ { for j:=i; j < 6*i + 6; j++ { if i == 0{ s[i][j] = 1 } else { tmp := 0 for k:=max(0, j - 6); k < j; k++ { tmp += s[i - 1][k] } s[i][j] = tmp } } } for i:=x-1; i<6*n; i++ { t += s[n-1][i] } m = 1 for i:=0; i<n; i++ { m = m * 6 } g := gcd(t, m) t = t / g m = m / g return } func main() { var n, x int fmt.Scan(&n, &x) t, m := f(n, x) if t == 0 { fmt.Println(0) } else if t == m { fmt.Println(1) } else { fmt.Printf("%d/%d", t, m) } } func max(a, b int) int { if a > b { return a } else { return b } }