【题解】选数字 [51nod1354]

【题解】选数字 [51nod1354]

传送门：选数字 ([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
",dp[K]);
    }
}