2338. Count the Number of Ideal Arrays
我以為是用dp
結果是他馬的排列組合
思路 :
找出結尾是i的ideal array有幾個
根據題意我們可以知道如果結尾是i，那前面的所有元素都會是i的因數
更準確地說：就是把i進行質因數分解後，把所有質因數分散在0~n-1的位置
看這樣可以得到幾種組合，高中數學自己回去複習一下
假設i做質因數分解後 i = P1^e1 * P2^e2 * P3^e3 * .... * Pk^ek
那總共會有C(n-1+e1,e1) * C(n-1+e2,e2) * C(n-1+e3,e3) * ... * C(n-1+ek,ek)種組合
就這樣答案就可以出來了
ｇｏｌａｎｇ　ｃｏｄｅ　：　
const (
MOD = 1_000_000_007
MAX_N = 10001
MAX_P = 14 // is max possible numbers of prime 2^14 > 10000
)
var (
cnk [MAX_N + MAX_P][MAX_P + 1]int
primeNum [MAX_N][]int
minPrime [MAX_N]int
)
func cInit() {
if cnk[0][0] !=0{
return
}
primeFactories()
cnk[0][0] = 1
for i := 1; i < MAX_N+MAX_P; i++ {
cnk[i][0] = 1
for j := 1; j <= min(i, MAX_P); j++ {
cnk[i][j] = (cnk[i-1][j] + cnk[i-1][j-1]) % MOD
}
}
}
func findMinPrime() {
for i := 2; i < MAX_N; i++ {
if minPrime[i] == 0 {
for j := i; j < MAX_N; j += i {
if minPrime[j] == 0 {
minPrime[j] = i
}
}
}
}
}
func primeFactories() {
findMinPrime()
for i := 2; i < MAX_N; i++ {
n := i
for n > 1 {
p, cnt := minPrime[n], 0
for n%p == 0 {
cnt++
n /= p
}
primeNum[i] = append(primeNum[i], cnt)
}
}
}
func idealArrays(n int, maxValue int) int {
ans := 1
cInit()
for i := 2; i <= maxValue; i++ {
tmp := 1
for _, val := range primeNum[i] {
tmp = tmp * cnk[n-1+val][val] % MOD
}
ans = (ans + tmp) % MOD
}
return ans
}

大師