51nod 1354 选数字 (01背包问题好题)-阿里云开发者社区

51nod 1354 选数字 (01背包问题好题)

2023-05-26 38

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 51nod 1354 选数字 (01背包问题好题)

当给定一个序列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取余之后输出即可。

输入样例

3 3

1 1 3

3 6

2 3 6

输出样例

思路：用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
*/

51nod 1354 选数字 (01背包问题好题)

热门文章

最新文章

相关电子书