当给定一个序列a[0],a[1],a[2],…,a[n-1] 和一个整数K时，我们想找出,有多少子序列满足这么一个条件：把当前子序列里面的所有元素乘起来恰好等于K。
样例解释：
对于第一个数据，我们可以选择[3]或者[1(第一个1), 3]或者[1(第二个1), 3]或者[1,1,3]。所以答案是4。
输入
多组测试数据。在输入文件的第一行有一个整数T(0< T <= 20)，表示有T组数据。
接下来的2*T行，会给出每一组数据
每一组数据占两行，第一行包含两个整数n, K(1<=n<=1000,2<=K<=100000000)他们的含意已经在上面提到。
第二行包含a[0],a[1],a[2],…,a[n-1] (1<= a[i]<=K) 以一个空格分开。
所有输入均为整数。
输出
对于每一个数据，将答案对1000000007取余之后输出即可。
输入样例
2
3 3
1 1 3
3 6
2 3 6
输出样例
4
2
思路：用map存当前存在的可以被k整除的值的数量，每次进来一个值，如果能被k整除，则乘上之前所有的情况看看能不能被k整除，如果可以，加入map里！
#include <bits/stdc++.h> using namespace std; const int maxn = 1e5 + 5; const int mod = 1e9 + 7; int a[maxn]; int b[maxn], cnt; bool cmp(int a, int b) { return a > b; } int main() { int n, T, k; cin >> T; while (T--) { cnt = 0; cin >> n >> k; for (int i = 1; i * i <= k; i++) { if (k % i == 0) { b[++cnt] = i; b[++cnt] = k / i; if (i == k / i)cnt--; } } sort (b + 1, b + cnt + 1, cmp); map<int,int> mp; mp.clear(); mp[1] = 1; for (int i = 1; i <= n; i++) { cin >> a[i]; for (int j = 1; j <= cnt; j++) { if (b[j] % a[i] == 0) { mp[b[j]] += mp[b[j]/a[i]]; mp[b[j]] %= mod; } } } cout << mp[k] << endl; } return 0; } /* 6 20 4 5 4 1 1 2 */
![洛谷P2871-[USACO07DEC]Charm Bracelet S（01背包模板题）](https://ucc.alicdn.com/images/user-upload-01/20200725131735571.png?x-oss-process=image/resize,h_160,m_lfit)