10.21模拟赛 猴猴吃香蕉（DP）

 1 #include<cstring>
 2 #include<queue>
 3 #include<cstdio>
 4 #include<iostream>
 5 #include<cmath>
 6 #include<algorithm>
 7 #include<vector>
 8 using namespace std;
 9 typedef long long ll;
10 const int mo=1e9+7;
11 const int maxm=1100;
12 int t,n,ans;
13 int k;
14 int a[maxm];
15 bool flag[maxm];
16 int dp[1100000];
17 int main()
18 {
19  //freopen("banana.in","r",stdin);
20  //freopen("banana.out","w",stdout); 
21  scanf("%d",&t);
22  while(t--)
23  {
24    scanf("%d%d",&n,&k);
25    ans=0;
26    memset(dp,0,sizeof(dp));
27    for(int i=1;i<=n;i++)
28    {
29         scanf("%d",&a[i]);
30    }
31    dp[0]=1;
32    for(int i=1;i<=n;i++)
33    {
34       for(int j=k/a[i];j>=0;j--)
35       if(j==0) dp[a[i]]+=dp[0];
36       else dp[a[i]*j]=(dp[a[i]*j]+dp[j])%mo;
37    }
38     printf("%d\n",dp[k]);
39  }
40  return 0;
41 }

#include<cstring>
#include<queue>
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<map>
using namespace std;
typedef long long ll;
const int mo=1e9+7;
const int maxm=1100;
int t,n,tot;
int k;
int a[maxm];
int b[maxm];
map<int,int>dp;
int main()
{
 freopen("banana.in","r",stdin);
 freopen("banana.out","w",stdout); 
 scanf("%d",&t);
 while(t--)
 {
   dp.clear();
   tot=0;
   scanf("%d%d",&n,&k);
   for(int i=1;i<=n;i++)
   {
        scanf("%d",&a[i]);
   }
   for(int i=1;i<=sqrt(k);i++)
   {
        if(k%i==0)
        {
            b[++tot]=i;
            if(i*i!=k)
            b[++tot]=k/i;
        }
   }
   sort(b+1,b+tot+1);
   for(int i=1;i<=n;i++)
   {
      if(a[i]==0) continue;
      for(int j=tot;j>=1;j--)
      {
       if(b[j]%a[i]==0)
       {
         dp[b[j]]=(dp[b[j]]+dp[b[j]/a[i]])%mo;
       }
       if(b[j]==a[i])//还可以就是自己
       dp[a[i]]+=1,dp[a[i]]%=mo;
      }
   }
    printf("%d\n",dp[k]);
 }
 return 0;
}