正题
题目链接:https://www.51nod.com/Contest/Problem.html#contestProblemId=1149
题目大意
n
n
n个数，求有多少种选择方案使选择的数乘机为
k
k
k。
解题思路
显然
k
k
k的质因数最多只有
9
9
9个，我们将质因数进行
d
p
dp
dp。若选择的数的质因数刚好是
k
k
k的质因数，那么就可以。
为了方便我们将状态压成一维的即可。
c
o
d
e
code
code
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std
;
const ll N
=1100,XJQ
=1e9+7;
struct node
{
ll w
,v
;
}q
[N
];
bool cmp(node x
,node y
)
{return x
.w
<y
.w
;}
ll n
,K
,v
[N
],sum
[N
],f
[N
*N
],T
,cnt
,two
;
void dfs(ll x
,ll s
,ll zs
)
{
if(x
>cnt
){
(f
[zs
]+=f
[s
])%=XJQ
;
return;
}
for(ll i
=q
[x
].v
-v
[x
];i
>=0;i
--)
dfs(x
+1,s
+sum
[x
-1]*i
,zs
+sum
[x
-1]*(i
+v
[x
]));
}
int main()
{
scanf("%lld",&T
);
while(T
--){
scanf("%lld%lld",&n
,&K
);cnt
=0;
for(ll i
=2;i
*i
<=K
;i
++){
if(!(K
%i
)){
q
[++cnt
].w
=i
;
q
[cnt
].v
=0;
while(!(K
%i
))
q
[cnt
].v
++,K
/=i
;
}
}
if(K
!=1) q
[++cnt
].w
=K
,q
[cnt
].v
=1;
sort(q
+1,q
+1+cnt
,cmp
);
memset(f
,0,sizeof(f
));
f
[0]=sum
[0]=two
=1;
for(ll i
=1;i
<=cnt
;i
++)
sum
[i
]=sum
[i
-1]*(q
[i
].v
+1);
for(ll i
=1;i
<=n
;i
++){
ll x
=0,z
=0,l
=0,r
=1;
bool flag
=0;
scanf("%lld",&x
);
if(x
==1){
two
=two
*2%XJQ
;
continue;
}
memset(v
,0,sizeof(v
));
for(ll j
=2;j
*j
<=x
;j
++){
if(!(x
%j
)){
while(q
[l
].w
<j
) r
*=v
[l
],l
++;
if(q
[l
].w
!=j
){flag
=1;break;}
while(!(x
%j
))
x
/=j
,v
[l
]+=(q
[l
].w
==j
);
if(v
[l
]>q
[l
].v
){flag
=1;break;}
}
}
if(flag
) continue;
if(x
!=1){
for(l
=0,r
=1;q
[l
].w
<x
;r
*=v
[l
],l
++);
if(q
[l
].w
==x
)v
[l
]++;
}
dfs(1,0,0);
}
printf("%lld\n",(f
[sum
[cnt
]-1]*two
)%XJQ
);
}
}
