题目描述
小美有一个数组，她希望删除kkk个元素，使得剩余的元素两两之间互为倍数关系。你能告诉小美有多少种删除方案吗？由于答案过大，请对10^9+7取模。
输入描述:第一行输入两个整数 n,k(1≤k≤n≤10^3)表示数组长度，删除的元素数量。第二行输入 n 个整数表示数组 a(1≤ai≤10^9)。保证给定的数组中不存在两个相等元素。
输出描述:输出一个整数表示答案。
输入
6 4
1 4 2 3 6 7
输出 8
说明
方案1：删除1,4,2,7
方案2：删除1,4,3,7。
方案3：删除1,3,6,7。
方案4：删除4,2,3,6。
方案5：删除4,2,3,7。
方案6：删除4,2,6,7。
方案7：删除4,3,6,7。
方案8：删除2,3,6,7。
#include <iostream> #include <vector> #include<bits/stdc++.h> #include <algorithm> using namespace std; const int N = 1e9 + 7; int a[1010]; int dp[1010][30]; int main() { int n, k; cin>>n>>k; for(int i = 1; i <= n; ++i) { cin>>a[i]; } sort(a+1, a+n+1); int cnt = n-k; if(cnt>29) { cout<<"0"<<endl; return 0; } int ans = 0; dp[1][1] = 1; for(int i = 1; i <= n; ++i) { dp[i][1] = 1; for(int j = 1; j < i; ++j) { if(a[i] % a[j] == 0) { for(int k = 2; k <=cnt; ++k) { dp[i][k]=(dp[i][k]+dp[j][k-1])% N; } } } } if(cnt > 29){ cout<<0; return 0; } for(int i = 2; i <= n; ++i) { ans = (ans + dp[i][cnt]) % N; } cout<<ans; return 0; }
