首页 > 代码库 > 51nod 1354：选数字
51nod 1354：选数字
51nod 1354：选数字
题目链接：http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1354
题目大意：有$T(T \leqslant 20)$组数据，每组给出$n(n \leqslant 1000)$个数和$K(K \leqslant 100,000,000)$，问在这$n$个数中选取若干个，积为$K$的方案数有多少.
DP+离散化
与01背包类似，定义状态$dp[i][j]$为前$i$个数中选取若干个数，积为$j$的方案数.
但积过大（$K \leqslant 100,000,000$），考虑到实际有用状态并不多，有用状态为$dp[i][d]$，其中$d$为$K$的因数.
故可以预处理出$K$的因数，将其离散化，从而把第二维降到$D(K)$，$D(K)$表示$K$的因子数.
算法时间复杂度为$O(n \times D(K) \times lg(D(K)))$，$lg$为离散化所带来的时间.
代码如下：
1 #include <iostream> 2 #include <algorithm> 3 #include <cstdio> 4 #include <cstring> 5 #define N 1005 6 using namespace std; 7 typedef long long ll; 8 const ll M=1000000007; 9 int T,n,K,a[N],k,fact[N],dp[N][N],t,ans;10 int main(void){11 scanf("%d",&T);12 while(T--){13 memset(dp,0,sizeof(dp));14 scanf("%d%d",&n,&K);15 for(t=1,k=0;t*t<K;++t)if(K%t==0){16 fact[k++]=t;17 fact[k++]=K/t;18 }if(K==t*t)fact[k++]=t;19 sort(fact,fact+k);20 for(int i=1;i<=n;++i){21 scanf("%d",&a[i]);22 for(int j=0;j<k;++j)if(dp[i-1][j]){23 dp[i][j]=(dp[i][j]+dp[i-1][j])%M;24 if((ll)K%((ll)fact[j]*a[i]))continue;25 t=lower_bound(fact,fact+k,fact[j]*a[i])-fact;26 dp[i][t]=(dp[i][t]+dp[i-1][j])%M;27 }28 if(K%a[i])continue;29 t=lower_bound(fact,fact+k,a[i])-fact;30 dp[i][t]=(dp[i][t]+1)%M;31 }32 printf("%d\n",dp[n][k-1]);33 }34 }
51nod 1354：选数字
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。