fork download
copy 
  1. /*
  2. Hey there, I love you. :D 
  3.  
  4. Yansoon.......
  5. */
  6.  
  7.  
  8. #include <bits/stdc++.h>
  9. #define ll long long
  10. #define ull unsigned long long
  11. #define all(o) o.begin(), o.end()
  12. #define rall(o) o.rbegin(), o.rend()
  13. #define setIO(name)                  \
  14.     freopen(name ".in", "r", stdin); \
  15.     freopen(name ".out", "w", stdout)
  16.  
  17. #ifdef DEBUG
  18. #include "debug.hpp"
  19. #else
  20. #define debug(...)
  21. #define debug_itr(...)
  22. #define debug_bits(...)
  23. #define debug_pq(...)
  24. #define debug_q(...)
  25. #endif
  26.  
  27. using namespace std;
  28.  
  29. const ull MOD = 1e9 + 7;
  30. const double PI = 3.14159265358979323846;
  31.  
  32. void file()
  33. {
  34. #ifdef DEBUG
  35.     freopen("in.txt", "r", stdin);
  36.     freopen("out.txt", "w", stdout);
  37. #endif
  38. }
  39.  
  40. ull power(ull b, ull p, ull m)
  41. {
  42.     if (p == 0) return 1;
  43.     ull sq = power(b, p / 2, m);
  44.     sq = sq * sq;
  45.  
  46.     if (p%2 == 1)
  47.         sq =  sq*b;
  48.     sq %= m;
  49.     return sq;
  50. }
  51. ull Combinations(ull n, ull r) {
  52.     if (r > n - r) r = n - r; // Use the smaller value for efficiency
  53.  
  54.     ull result = 1;
  55.     for (ull i = 1; i <= r; i++) {
  56.         result = result * (n - i + 1) / i;
  57.     }
  58.  
  59.     return result;
  60. }
  61. ll gcd(ll a,ll b)
  62. {
  63.     if (b == 0) return a;
  64.  
  65.     return gcd(b, a%b);
  66. }
  67. const ll mod = (ll)1e9 + 7;
  68. ll dp[1000005];
  69. int n, x;
  70. ll c[105];
  71. ll ac(ll sum)
  72. {
  73.     if (sum > x) return 0;
  74.     else if(sum == x) return 1;
  75.  
  76.     ll &ret = dp[sum];
  77.  
  78.     if (ret != -1) return ret;
  79.  
  80.     ll ans = 0;
  81.     for (int i = 0;i < n;i++)
  82.     {
  83.         ans += ac(sum + c[i]);
  84.         ans %= mod;
  85.     }
  86.     return ret = ans;
  87. }
  88. void solve()
  89. {
  90.     memset(dp, -1, sizeof(dp));
  91.     cin >> n >> x;
  92.     for (int i = 0; i < n;i++)
  93.         cin >> c[i];
  94.  
  95.     ll ans = ac(0);
  96.     cout << ans << endl;
  97. }
  98.  
  99. int main()
  100. {
  101.     ios_base::sync_with_stdio(false);
  102.     cin.tie(NULL);
  103.     file();
  104.     int t = 1;
  105.     // cin >> t;
  106.     while (t--)
  107.         solve();
  108.     return 0;
  109. }
Success #stdin #stdout 0.01s 11348KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/0lBJcW
language:
C++14 (clang 8.0)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!