Submission #6358346

---

Source Code Expand

package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

func getScanner(fp *os.File) *bufio.Scanner {
	scanner := bufio.NewScanner(fp)
	scanner.Split(bufio.ScanWords)
	scanner.Buffer(make([]byte, 500001), 500000)
	return scanner
}

func getNextString(scanner *bufio.Scanner) string {
	scanner.Scan()
	return scanner.Text()
}

func getNextInt(scanner *bufio.Scanner) int {
	i, _ := strconv.Atoi(getNextString(scanner))
	return i
}

func getNextInt64(scanner *bufio.Scanner) int64 {
	i, _ := strconv.ParseInt(getNextString(scanner), 10, 64)
	return i
}

func main() {
	fp := os.Stdin
	if len(os.Args) > 1 {
		fp, _ = os.Open(os.Args[1])
	}

	scanner := getScanner(fp)

	writer := bufio.NewWriter(os.Stdout)

	n := getNextInt(scanner)
	d := getNextInt64(scanner)

	fmt.Fprintln(writer, solve(n, d))

	writer.Flush()
}

func solve(n int, d int64) float64 {
	dp := preCalc(n, d)

	cc := make([]int, 3)

	for d%5 == 0 {
		cc[0]++
		d /= 5
	}
	for d%3 == 0 {
		cc[1]++
		d /= 3
	}
	for d%2 == 0 {
		cc[2]++
		d /= 2
	}
	if d != 1 {
		return 0.0
	}

	ans := 1.0

	for i := 0; i < len(dp); i++ {
		for ii := 0; ii < len(dp[i]); ii++ {
			for iii := 0; iii < len(dp[i][ii]); iii++ {
				if i < cc[0] || ii < cc[1] || iii < cc[2] {
					ans -= dp[i][ii][iii]
				}
			}
		}
	}

	return ans
}

func preCalc(n int, d int64) [][][]float64 {
	var dp [2][][][]float64
	max := uint64(0xffffffffffffffff)
	var i5, i3, i2 uint64
	n5 := 0
	n3 := 0
	n2 := 0
	for i5 = max; i5 > 0; i5 /= 5 {
		n5++
	}
	for i3 = max; i3 > 0; i3 /= 3 {
		n3++
	}
	for i2 = max; i2 > 0; i2 /= 2 {
		n2++
	}
	dp[0] = make([][][]float64, n5+1)
	dp[1] = make([][][]float64, n5+1)
	for i := 0; i < n5+1; i++ {
		dp[0][i] = make([][]float64, n3+1)
		dp[1][i] = make([][]float64, n3+1)
		for ii := 0; ii < n3+1; ii++ {
			dp[0][i][ii] = make([]float64, n2+1)
			dp[1][i][ii] = make([]float64, n2+1)
		}
	}
	dp[0][0][0][0] = 1.0

	p := 0
	c := 1

	for index := 0; index < n; index++ {
		for i := 0; i <= n5; i++ {
			for ii := 0; ii <= n3; ii++ {
				for iii := 0; iii <= n2; iii++ {
					// 1
					dp[c][i][ii][iii] = dp[p][i][ii][iii] / 6.0
					// 2
					if iii > 0 {
						dp[c][i][ii][iii] += dp[p][i][ii][iii-1] / 6.0
					}
					// 3
					if ii > 0 {
						dp[c][i][ii][iii] += dp[p][i][ii-1][iii] / 6.0
					}
					// 4
					if iii >= 2 {
						dp[c][i][ii][iii] += dp[p][i][ii][iii-2] / 6.0
					}
					// 5
					if i > 0 {
						dp[c][i][ii][iii] += dp[p][i-1][ii][iii] / 6.0
					}
					// 6
					if ii > 0 && iii > 0 {
						dp[c][i][ii][iii] += dp[p][i][ii-1][iii-1] / 6.0
					}
				}
			}
		}
		c, p = p, c
	}

	return dp[p]
}

Submission Info

Judge Result