51Nod-1354 选数字(dp，思路)

2023-10-05 23:31

文章标签 dp 51nod 数字思路 1354

本文主要是介绍51Nod-1354 选数字(dp，思路)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

描述

当给定一个序列a[0],a[1],a[2],…,a[n-1]
和一个整数K时，我们想找出,有多少子序列满足这么一个条件：把当前子序列里面的所有元素乘起来恰好等于K。

样例解释：

对于第一个数据，我们可以选择[3]或者[1(第一个1), 3]或者[1(第二个1), 3]或者[1,1,3]。所以答案是4。

Input

多组测试数据。在输入文件的第一行有一个整数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) 以一个空格分开。所有输入均为整数。

Output

对于每一个数据，将答案对1000000007取余之后输出即可。

Input示例

Output示例

4
2

思路

定义dp[i]表示：i是k的约数的情况下，原序列的子序列中所有元素乘积为i个子序列个数

然后利用一个map来存储，每一次输入一个新数时，就让这个新数和map中所有元素相乘，当乘积是k的约数时，就记录一下，然后更新一下map[a[i]]的值

代码

#include <cstdio>
#include <cstring>
#include <cctype>
#include <stdlib.h>
#include <string>
#include <map>
#include <iostream>
#include <stack>
#include <cmath>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
#define inf 1000000
#define mem(a,b) memset(a,b,sizeof(a))
const int mod=1000000007;
const int N=1000+7;
int a[N];
map<int,int>dp;
map<int,int>temp;
int main()
{int t,n,k;scanf("%d",&t);while(t--){dp.clear();temp.clear();scanf("%d%d",&n,&k);map<int,int>::iterator it;for(int i=1; i<=n; i++){scanf("%d",&a[i]);if(k%a[i]==0){temp=dp;for(it=temp.begin(); it!=temp.end(); it++){int tmp=a[i]*it->first;//当前枚举的数和容器里面的元素各个乘积if(k%tmp==0)//k是这些乘积的个数dp[tmp]=(dp[tmp]+it->second)%mod;//更新dp[tmp]}dp[a[i]]=(dp[a[i]]+1)%mod;//更新乘积为a[i]的个数}}printf("%d\n",dp[k]);}return 0;
}