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

简介: 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取余之后输出即可。

输入样例

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
*/
相关文章
|
算法 编译器 C++
【C/C++ 泛型编程 应用篇】C++ 如何通过Type traits 判断 Lambda表达式类型?
【C/C++ 泛型编程 应用篇】C++ 如何通过Type traits 判断 Lambda表达式类型?
204 4
在代码优化过程中,常见的错误和bug包括以下几点
在代码优化过程中,常见的错误和bug包括以下几点
浅析Qt Designer设置界面背景-运用PyCharm中把pyrcc5将.qrc转换为.py存在的一些问题
浅析Qt Designer设置界面背景-运用PyCharm中把pyrcc5将.qrc转换为.py存在的一些问题
浅析Qt Designer设置界面背景-运用PyCharm中把pyrcc5将.qrc转换为.py存在的一些问题
|
安全 Java 开发者
Java一分钟之-Spring Cloud Netflix Eureka:服务注册与发现
【6月更文挑战第8天】Spring Cloud Eureka是微服务架构的关键,提供服务注册与发现功能。本文讲解Eureka工作原理、配置、常见问题及解决方案。Eureka包含Server(管理服务状态)和Client(注册服务实例并发现服务)。快速入门包括启动Eureka Server和创建Eureka Client。常见问题涉及服务注册不上、服务下线和客户端注册信息不准确,可通过检查网络、理解自我保护机制和配置元数据解决。此外,文中还提及健康检查、安全配置和集群部署等高级实践,以增强系统健壮性和扩展性。
388 8
|
存储 关系型数据库 分布式数据库
PolarDB介绍
PolarDB是阿里巴巴自研的新一代云原生数据库
206 1
|
数据采集 人工智能 自然语言处理
GPT大升级!它可以在哪些场景辅助数据采集?
用ChatGPT辅助数据采集,XPath、正则表达式都能写!
|
Windows
windows 技巧篇-查看文件夹被那个进程占用,文件夹占用解除方法
windows 技巧篇-查看文件夹被那个进程占用,文件夹占用解除方法
2118 0
windows 技巧篇-查看文件夹被那个进程占用,文件夹占用解除方法
|
安全 网络安全 数据安全/隐私保护
网络安全攻击方式之"社会工程学"
网络安全攻击方式之"社会工程学"
|
开发工具 git
git项目代码一次push,同时上传到多个git仓库地址,并保证多个仓库代码同步一致
git项目代码一次push,同时上传到多个git仓库地址,并保证多个仓库代码同步一致
git项目代码一次push,同时上传到多个git仓库地址,并保证多个仓库代码同步一致
|
消息中间件 存储 算法
Kafka 如何保证数据不丢失
Kafka 如何保证数据不丢失
2563 0
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等

登录插画

登录以查看您的控制台资源

管理云资源
状态一览
快捷访问