http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1354&judgeId=187448
其实这题和在若干个数字中，选取和为val，有多少种不同的选法是一样的。
只不过不能直接枚举背包容量，只能用map的iterate来枚举，这样来加速。
还有一个剪枝就是，所生成的数字要是val的约数，这些才加入去map那里，否则不加。
都是一些没用的状态。
还有这题不能用map的reverse_iterator，会蜜汁wa
#include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <algorithm> #include <assert.h> #define IOS ios::sync_with_stdio(false) using namespace std; #define inf (0x3f3f3f3f) typedef long long int LL; #include <iostream> #include <sstream> #include <vector> #include <set> #include <map> #include <queue> #include <string> #include <hash_map> using namespace __gnu_cxx; const int MOD = 1000000007; map<int, int>dp; void init() { dp.clear(); } void work() { init(); int n, val; scanf("%d%d", &n, &val); dp[1] = 1; for (int i = 1; i <= n; ++i) { int x; scanf("%d", &x); //// if (val % x != 0) continue; // for (map<int, int> :: reverse_iterator it = dp.rbegin(); it != dp.rend(); ++it) { // if (val / it->first < x) continue; // if (val % (it->first * x) != 0) continue; //// dp[it->first * x] = (dp[it->first * x] + (it->second)) % MOD; // dp[it->first * x] += it->second; // dp[it->first * x] %= MOD; // } map<int, int> :: iterator it = dp.end(); it--; for(;; --it) { LL t = 1LL * it->first * x; if (t <= val && val % t == 0) { dp[t] += it->second; dp[t] %= MOD; } if (it == dp.begin()) break; } } printf("%d ", dp[val]); } int main() { #ifdef local freopen("data.txt", "r", stdin); // freopen("data.txt", "w", stdout); #endif int t; scanf("%d", &t); while (t--) work(); return 0; }