正題

題目鏈接:https://www.51nod.com/Contest/Problem.html#contestProblemId=1149

---

題目大意

$n$個數(shù)，求有多少種選擇方案使選擇的數(shù)乘機為$k$。

---

解題思路

顯然$k$的質(zhì)因數(shù)最多只有$9$個，我們將質(zhì)因數(shù)進行$dp$。若選擇的數(shù)的質(zhì)因數(shù)剛好是$k$的質(zhì)因數(shù)，那么就可以。

為了方便我們將狀態(tài)壓成一維的即可。

---

$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);} }

總結(jié)

以上是生活随笔為你收集整理的51nod-猴猴吃香蕉【dp】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。