首页 > 代码库 > SRM632 Div2 1000 DP
SRM632 Div2 1000 DP
【题意】：
给你一个值v和一组数字，求在这组数字中有多少种可用的组合，可用的组合意思是组合中数字乘积等于这个v（不同位置的数组成的相同情况视为不同的解）。
【知识点】：DP
【题解】：
声明map<LL, LL> mp; 第一个元素代表能整除v的一个数，第二个元素代表数字组前i个元素中乘积为该数的集合数。
然后遍历这组数字，mp[v]的值即为答案。 当v为1时，要特判减1。
【代码】：
1 #include <cstdio> 2 #include <string> 3 #include <vector> 4 #include <map> 5 using namespace std; 6 7 #define LL long long 8 9 class GoodSubset{10 public:11 map<int, int> mp;12 int numberOfSubsets(int goodValue, vector <int> d){13 const LL MOD = 1000000007;14 map<LL, LL> mp;15 mp[1] = 1;16 map<LL, LL>::reverse_iterator it;17 for(int i = 0; i < d.size(); i++){18 LL val = d[i];19 for(it = mp.rbegin(); it != mp.rend(); it++){20 LL z = it->first; z *= val;21 if(goodValue % z == 0){22 mp[z] = (mp[z] + it->second) % MOD;23 }24 }25 }26 mp[1]--;27 return mp[goodValue];28 }29 };
SRM632 Div2 1000 DP
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。