2026-06-21：统计结果等于 K 的序列数目。用go语言，给定整数数组 nums 和整数 k。 从左到右遍历 nums，维护一个初始值 val = 1。到达

package main

import (
    "fmt"
    "math/bits"
)

// 返回 k 中的质因子 2,3,5 的个数，以及 k 是否只包含 <= 5 的质因子
func primeFactorization(k int) ([3]int, bool) {
    e2 := bits.TrailingZeros(uint(k))
    k >>= e2

    e3 := 0
    for k%3 == 0 {
        e3++
        k /= 3
    }

    e5 := 0
    for k%5 == 0 {
        e5++
        k /= 5
    }

    return [3]int{e2, e3, e5}, k == 1
}

func countSequences(nums []int, k int64)int {
    e, ok := primeFactorization(int(k))
    if !ok { // k 有大于 5 的质因子
        return0
    }

    n := len(nums)
    es := make([][3]int, n)
    for i, x := range nums {
        es[i], _ = primeFactorization(x)
    }

    type args struct{ i, e2, e3, e5 int }
    memo := map[args]int{}

    var dfs func(int, int, int, int)int
    dfs = func(i, e2, e3, e5 int)int {
        if i < 0 {
            if e2 == 0 && e3 == 0 && e5 == 0 { // k 变成 1
                return1
            }
            return0
        }
        p := args{i, e2, e3, e5}
        if res, ok := memo[p]; ok {
            return res
        }

        e := es[i]
        res1 := dfs(i-1, e2-e[0], e3-e[1], e5-e[2]) // k 除以 nums[i]
        res2 := dfs(i-1, e2+e[0], e3+e[1], e5+e[2]) // k 乘以 nums[i]
        res3 := dfs(i-1, e2, e3, e5)                // k 不变
        res := res1 + res2 + res3

        memo[p] = res
        return res
    }

    return dfs(n-1, e[0], e[1], e[2]) // 从 k 开始，目标是变成 1
}

func main() {
    nums := []int{2, 3, 2}
    k := 6
    result := countSequences(nums, int64(k))
    fmt.Println(result)
}

# -*-coding:utf-8-*-

from typing import List, Tuple
from functools import lru_cache

def prime_factorization(k: int) -> Tuple[Tuple[int, int, int], bool]:
    """
    返回 k 中的质因子 2,3,5 的个数，以及 k 是否只包含 <= 5 的质因子
    """
    e2 = 0
    while k % 2 == 0:
        e2 += 1
        k //= 2
    
    e3 = 0
    while k % 3 == 0:
        e3 += 1
        k //= 3
    
    e5 = 0
    while k % 5 == 0:
        e5 += 1
        k //= 5
    
    return (e2, e3, e5), k == 1

def count_sequences(nums: List[int], k: int) -> int:
    """
    计算满足条件的序列数量
    """
    # 获取 k 的质因子分解
    k_factors, ok = prime_factorization(k)
    if not ok:  # k 有大于 5 的质因子
        return0
    
    n = len(nums)
    
    # 预先计算每个 nums[i] 的质因子分解
    factors = []
    for x in nums:
        f, _ = prime_factorization(x)
        factors.append(f)
    
    # 使用 lru_cache 实现记忆化搜索
    @lru_cache(None)
    def dfs(i: int, e2: int, e3: int, e5: int) -> int:
        """
        i: 当前处理的索引
        e2, e3, e5: 当前 k 中质因子 2,3,5 的指数
        """
        if i < 0:
            # 当所有数都处理完，如果 k 变为 1，则找到一种方案
            return1if e2 == 0 and e3 == 0 and e5 == 0else0
        
        # 获取当前数的质因子指数
        f2, f3, f5 = factors[i]
        
        # 三种操作：
        # 1. k 除以 nums[i]（需要 k 能被整除）
        # 2. k 乘以 nums[i]
        # 3. k 不变
        res = 0
        
        # 操作1: k 除以 nums[i]
        res += dfs(i - 1, e2 - f2, e3 - f3, e5 - f5)
        
        # 操作2: k 乘以 nums[i]
        res += dfs(i - 1, e2 + f2, e3 + f3, e5 + f5)
        
        # 操作3: k 不变
        res += dfs(i - 1, e2, e3, e5)
        
        return res
    
    # 从最后一个元素开始，初始状态为 k 的质因子指数
    return dfs(n - 1, k_factors[0], k_factors[1], k_factors[2])

def main():
    nums = [2, 3, 2]
    k = 6
    result = count_sequences(nums, k)
    print(result)

if __name__ == "__main__":
    main()

#include <iostream>
#include <vector>
#include <map>
#include <tuple>
#include <array>

using namespace std;

// 返回 k 中质因子 2,3,5 的个数，以及 k 是否只包含 <= 5 的质因子
bool primeFactorization(int k, array<int, 3>& e) {
    e[0] = 0;
    while (k % 2 == 0) {
        ++e[0];
        k /= 2;
    }
    e[1] = 0;
    while (k % 3 == 0) {
        ++e[1];
        k /= 3;
    }
    e[2] = 0;
    while (k % 5 == 0) {
        ++e[2];
        k /= 5;
    }
    return k == 1;
}

int dfs(int i, int e2, int e3, int e5,
        const vector<array<int, 3>>& es,
        map<tuple<int, int, int, int>, int>& memo) {
    if (i < 0) {
        return (e2 == 0 && e3 == 0 && e5 == 0) ? 1 : 0;
    }
    auto key = make_tuple(i, e2, e3, e5);
    auto it = memo.find(key);
    if (it != memo.end()) return it->second;

    const auto& e = es[i];
    int res1 = dfs(i - 1, e2 - e[0], e3 - e[1], e5 - e[2], es, memo); // 除以 nums[i]
    int res2 = dfs(i - 1, e2 + e[0], e3 + e[1], e5 + e[2], es, memo); // 乘以 nums[i]
    int res3 = dfs(i - 1, e2, e3, e5, es, memo);                      // 不变
    int res = res1 + res2 + res3;
    memo[key] = res;
    return res;
}

int countSequences(const vector<int>& nums, long long k) {
    array<int, 3> e;
    if (!primeFactorization(static_cast<int>(k), e)) {
        return0; // k 有大于 5 的质因子
    }

    int n = nums.size();
    vector<array<int, 3>> es(n);
    for (int i = 0; i < n; ++i) {
        primeFactorization(nums[i], es[i]);
    }

    map<tuple<int, int, int, int>, int> memo;
    return dfs(n - 1, e[0], e[1], e[2], es, memo);
}

int main() {
    vector<int> nums = {2, 3, 2};
    long long k = 6;
    int result = countSequences(nums, k);
    cout << result << endl;
    return0;
}