coin_combinations_i_1635.cpp (507B)
1 #include <iostream> 2 #include <vector> 3 4 static constexpr int mod = 1000000007; 5 static constexpr int X = 1000001; 6 7 int f(const std::vector<int>& c, std::vector<int>& a, int x) { 8 if (x < 0) return 0; 9 if (a[x] != -1) return a[x]; 10 if (x == 0) return a[x] = 1; 11 12 a[x] = 0; 13 for (auto m : c) 14 a[x] = (a[x] + f(c, a, x-m)) % mod; 15 return a[x]; 16 } 17 18 int main() { 19 int n, x; 20 std::cin >> n >> x; 21 std::vector<int> c(n), a(X, -1); 22 for (int i = 0; i < n; i++) 23 std::cin >> c[i]; 24 std::cout << f(c, a, x) << "\n"; 25 }