coin_combinations_ii_1636.cpp (643B)
1 #include <iostream> 2 #include <map> 3 #include <vector> 4 5 static constexpr int mod = 1000000007; 6 static constexpr int X = 1000001; 7 8 int main() { 9 int n, x; 10 std::cin >> n >> x; 11 std::vector<int> c(n); 12 for (int i = 0; i < n; i++) 13 std::cin >> c[i]; 14 15 std::vector<std::vector<int>> a(n, std::vector<int>(X, 0)); 16 for (int i = 0; i < (int)c.size(); i++) a[i][0] = 1; 17 for (int j = c.back(); j <= x; j += c.back()) a[c.size()-1][j] = 1; 18 for (int i = c.size()-2; i >= 0; i--) { 19 for (int j = 1; j <= x; j++) { 20 a[i][j] = a[i+1][j]; 21 if (j >= c[i]) { 22 a[i][j] += a[i][j-c[i]]; 23 a[i][j] %= mod; 24 } 25 } 26 } 27 std::cout << a[0][x] << "\n"; 28 }