【题解】选数字 [51nod1354]
【题目描述】
共 \(T\) 组测试点，每一组给定一个长度为 \(n\) 的序列和一个整数 \(K\)，找出有多少子序列满足子序列中所有元素乘积恰好等于K，答案对 \(1e9+7\) 取模。
【样例】
样例输入：
2
3 3
1 1 3
3 6
2 3 6
样例输出：
4
2
【数据范围】
\(100\%\) \(1 \leqslant T \leqslant 20,\) \(1 \leqslant N \leqslant 1000,\) \(2 \leqslant K \leqslant 10^8,\) \(1 \leqslant a[i] \leqslant K\)
【分析】
考虑 \(01\) 背包，用 \(dp[j]\) 表示乘积等于 \(j\) 的子序列数，原序列中的 \(n\) 个数就是 \(n\) 个物品，其数值就是体积。
\(K\) 的范围有 \(10^8\) 辣莫大，但是会对答案造成影响的只有一部分可整除 \(K\) 的数的 \(dp\) 值，所以还可以优化。
为防止爆空间，\(dp\) 数组开 \(map\) 类型，用指针访问，并且保证里面存的决策点都是可以整除 \(K\) 的数，每次要加入新的物品时判断一下，只有当物品体积 \(a\) 和 \(a\) 乘以决策点都可整除 \(K\) 时，才让该物品使用该决策点。
即 \(dp[a*x]+=dp[x](a|K,x|K,a*x|K)\) 。
时间复杂度为 \(O(T*n*p)\)，其中 \(p\) 为 \(K\) 的正约数个数。
【Code】
#include<algorithm>
#include<cstdio>
#include<map>
#define Re register int
using namespace std;
const int P=1e9+7;
const int N=1003;
int x,n,K,T,t,o,a;
map<int,int>dp,tmp;
map<int,int>::iterator it;
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
int main(){
in(T);
while(T--){
in(n),in(K);
dp.clear();
for(Re i=1;i<=n;++i){
in(a);
if(K%a)continue;
tmp=dp;
for(it=tmp.begin();it!=tmp.end();++it)
if(a<=K/(x=it->first)&&K/x%a==0)
(dp[a*x]+=it->second)%=P;
(dp[a]+=1)%=P;
}
printf("%d\n",dp[K]);
}
}