【51nod】猴猴吃香蕉【背包】

题目大意：

题目链接：http://www.51nod.com/Contest/Problem.html#contestProblemId=1149

猴猴最爱吃香蕉了。每天猴猴出门都会摘很多很多的香蕉，每个香蕉都有一个甜度，猴猴不一定要把所有的香蕉都吃掉，猴猴每天都有一个心情值K，猴猴希望当天吃的香蕉满足这么一个条件，这些香蕉的甜度乘积恰好等于K，但是猴猴并不知道有多少种方法，于是猴猴把这个问题交给你。

---

思路：

$m\le 10^8$，根据试除法的推论，$m$的约束不会超过$2\sqrt{m}=2\times 10^4$个。 所以我们求出$m$的所有因数并排序，然后设$f[i]$表示第组成第$i$个因数的方案数，那么我们对于读入的$x$，枚举$m$的所有因数$v$，如果$x$是$v$的因数，那么就有 $$f[pos[v]]=f[pos[v]]+f[pos[\frac{v}{x}]]$$ 其中$pos[x]$表示$x$是$m$的第几个因数。 最终答案是$f[k]$ 注意$m$的因数要从大到小排序，因为01背包是会覆盖原来顺序的。

---

代码：

#include <map> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int N=20010,MOD=1000000007; int T,n,m,x,k,f[N],v[N]; map<int,int> pos; int main() { scanf("%d",&T); while (T--) { memset(f,0,sizeof(f)); memset(v,0,sizeof(v)); k=0; pos.clear(); scanf("%d%d",&n,&m); for (int i=1;i*i<=m;i++) if (!(m%i)) { v[++k]=i; if (i*i!=m) v[++k]=m/i; } sort(v+1,v+1+k); for (int i=1;i<=k;i++) pos[v[i]]=i; f[1]=1; for (int i=1;i<=n;i++) { scanf("%d",&x); if(m%x!=0) continue; for (int j=k;j>=1;j--) if (!(v[j]%x)) f[j]=(f[j]+f[pos[v[j]/x]])%MOD; } printf("%d\n",f[pos[m]]); } return 0; }