→ sustainer123: 就暴力解喔 真假 04/12 19:43
→ sustainer123: 我直覺上有想到 但感覺hard又沒那麼白痴 04/12 19:43
推 scmono: 大師 我連題目讀懂都想好久== 04/12 19:46
推 Furina: 大師 04/12 20:00
3272. Find the Count of Good Integers
滿無聊的問題
寫起來很浪費時間
思路:
把所有n位數且是回文並可以被k整除的數字記錄下來
並且記錄該數字中0~9出現過的次數
接著就開始排列
最後回傳答案就好
golang code :
func countGoodIntegers(n int, k int) int64 {
if n == 1 {
return int64(9 / k)
}
rec := make(map[[10]int]bool)
if n&1 == 0 {
rec = chkEvenLen(n, k)
} else {
rec = chkOddLen(n, k)
}
ans := 0
for key := range rec {
tmp := 1
nTmp := n
tmp *= (cnk(nTmp, key[0]) - cnk(nTmp-1, key[0]-1))
nTmp -= key[0]
for i := 1; i < 10; i++ {
tmp *= cnk(nTmp, key[i])
nTmp -= key[i]
}
ans += tmp
}
return int64(ans)
}
func cnk(n, k int) int {
if k < 0 {
return 0
}
if k == n || k == 0 {
return 1
}
if k == 1 {
return n
}
if k > n/2 {
k = n - k
}
dp := make([]int, k+1)
dp[0] = 1
for i := 1; i <= n; i++ {
for j := min(i, k); j > 0; j-- {
dp[j] += dp[j-1]
}
}
return dp[k]
}
func chkOddLen(n int, k int) map[[10]int]bool {
res := make(map[[10]int]bool)
n /= 2
start, end := int(math.Pow10(n-1)), int(math.Pow10(n))-1
for i := 0; i < 10; i++ {
for j := start; j <= end; j++ {
s := strconv.Itoa(j)
s = s + string(byte('0'+i)) + reverseString(s)
tmp, _ := strconv.Atoi(s)
if tmp%k == 0 {
rec := [10]int{}
for key, _ := range s {
rec[int(s[key]-'0')]++
}
res[rec] = true
}
}
}
return res
}
func chkEvenLen(n int, k int) map[[10]int]bool {
res := make(map[[10]int]bool)
n /= 2
start, end := int(math.Pow10(n-1)), int(math.Pow10(n))-1
for j := start; j <= end; j++ {
s := strconv.Itoa(j)
s = s + reverseString(s)
tmp, _ := strconv.Atoi(s)
if tmp%k == 0 {
rec := [10]int{}
for key, _ := range s {
rec[int(s[key]-'0')]++
}
res[rec] = true
}
}
return res
}
func reverseString(s string) string {
runes := []rune(s)
for i, j := 0, len(runes)-1; i < j; i, j = i+1, j-1 {
runes[i], runes[j] = runes[j], runes[i]
}
return string(runes)
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.82.145.154 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1744457929.A.C97.html