当给定一个序列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示例 2 3 3 1 1 3 3 6 2 3 6 Output示例 4 2
题解 朴素DP类似于背包，考虑只有约数才能转移，所以在此DP上用map优化。
代码
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<set> #include<ctime> #include<vector> #include<cmath> #include<algorithm> #include<map> #define mod 1000000007 #define ll long long #define inf 1e9 using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,k; map<int,int>mp,dp; map<int,int>::iterator it; inline void solve() { n=read();k=read(); dp.clear(); for (int i=1;i<=n;i++) { int x=read(); if (k%x!=0) continue; mp=dp; for (it=mp.begin();it!=mp.end();it++) { int tmp=x*it->first; if (k%tmp!=0) continue; dp[tmp]=(dp[tmp]+it->second)%mod; } dp[x]=(dp[x]+1)%mod; } printf("%d\n",dp[k]); } int main() { int Case=read(); while (Case--) solve(); return 0; }