思路

反过来想，就是要从这个序列中选取n - k 个数的子序列，使得两两成倍数。

我们对序列排序之后，<两两成倍数> 这个性质具有同样的子问题。

比如x , y , z 符合这个性质，那么只要w > z 并且 w 是z的倍数。

这种情况下， x , y , z , w 也满足<两两成倍数>的性质。

那么我们自然想到使用动态规划，

状态:$dp[i]$ 代表以第i个数为结尾的合法子序列个数。(注意现在这个序列已经被我们排好序，只有排序才能使用dp)

转移：考虑[1 , i - 1] 之间所有是i的约数的数，假设这些数是j，那么把他们都加起来即可。

$dp[i] += dp[j]$

代码

C++

#include <bits/stdc++.h>
using namespace std;

const int MOD = 1e9 + 7;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    vector<int> a(n + 1);
    for (int i = 1; i <= n; ++i) cin >> a[i];

    if (n == m) {
        cout << "1\n";
        return 0;
    } 

    if (n == m + 1) {
        cout << n << "\n";
        return 0;
    }

    sort(a.begin(), a.end());

    // dp[0][0] = 1
    // dp[i][j] 表示前 i 个数，第 i 个数存在的情况下，保留 j 个数的方案数
    // 对于第 i 个数，如果不保留，那就是 dp[i - 1][j - 1]
    // 对于第 i 个数，如果保留，  那就是 sum(dp[k][j - 1])

    m = n - m;

    vector<vector<int>> dp(n + 1, vector<int>(m + 1));

    for (int i = 1; i <= n; ++i) {
        dp[i][1] = 1;
        for (int j = 2; j <= min(i, m); ++j) {
            for (int k = 1; k < i; ++k) {
                if (a[i] % a[k] == 0) {
                    dp[i][j] += dp[k][j - 1];
                    if (dp[i][j] >= MOD) dp[i][j] -= MOD;
                }
            }
        }
    }

    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        ans += dp[i][m];
        if (ans >= MOD) ans -= MOD;
    }

    cout << ans << "\n";

    return 0;
}

Java

import java.util.*;
class Main{
    public static void main(String[]args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int k=sc.nextInt();
        int t=n-k;
        long ans=0;
        long mod=1000000007;
        long[]nums=new long[n];
        if(t==1){
            ans=n;
        }
        else if(t==0){
            ans=1;
        }
        else if(t>=32){
            ans=0;
        }
        else{
        for(int i=0;i<n;i++){
            nums[i]=sc.nextLong();
        }
        Arrays.sort(nums);
        List<Integer>[]arr=new List[n];
        for(int i=0;i<n;i++){
            arr[i]=new ArrayList<>();
            for(int j=0;j<i;j++){
                if(nums[i]%nums[j]==0){
                    arr[i].add(j);
                }
            }
        }
        long[][]dp=new long[t+1][n+1];
        for(int i=1;i<=n;i++){
            dp[1][i-1]=1;
        }
        for(int i=2;i<=t;i++){
            for(int j=1;j<=n;j++){
                for(int x:arr[j-1]){
                    dp[i][j]=(dp[i][j]+dp[i-1][x])%mod;
                }
            }
        }

        for(int i=1;i<=n;i++){
            ans=(ans+dp[t][i])%mod;
        }
        }
        System.out.print(ans);
    }
}

Python

n, k = list(map(int, input().split()))
a = list(map(int, input().split()))

if n == k:
    print(1)
else:
    a = sorted(a)
    from collections import defaultdict
    dp = [[0] * (n+1) for _ in range(n)]
    res = 0
    for i in range(n):
        dp[i][1] = 1
        for j in range(i):
            if a[i] % a[j] == 0:
                for l in range(1,n):
                    dp[i][l+1] += dp[j][l]

    for i in range(n):
        for j in range(1, n+1):
            if j == n - k:
                res += dp[i][j]

    print(res)

题目描述

小美有一个长度为 $n$ 的数组 $a$ ，他希望删除恰好 $k$ 个数，使得这个数组是一个倍数数组。

倍数数组是指数组中任意两个数 $a$ 和 $b$ 都是倍数关系，要么 $a$ 是 $b$ 的倍数，要么 $b$ 是 $a$ 的倍数。

特别地，长度为 $1$ 和 $0$ 的数组也是倍数数组

现在，小美想问你有多少种不同的删除方案。

输入描述

第一行，两个整数 $n,k((1 \leq k \leq n \leq 10^3)$ 分别表示数组的长度，以及要删除的数的数量。
第二行，$n$ 个整数表示数组 $a$，第 $i$ 个数为 $a_i(1 \leq a_i \leq 10^9)$ 。

数据保证初始的数组 $a$ 中数两两不同。

输出描述

一个整数，表示不同的删除方案。

样例

输入

3 1
1 2 4

输出

3

说明

方案1：删除 1。
方案2：删除 2。
方案3：删除 4。