fork download
copy 
  1. #include <bits/stdc++.h>
  2. #include <algorithm>
  3. using namespace std;
  4.  
  5. #include <ext/pb_ds/assoc_container.hpp>
  6. #include <ext/pb_ds/tree_policy.hpp>
  7.  
  8. using namespace __gnu_pbds;
  9. template<typename T>
  10. using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  11. #define int long long
  12. #define ll long long
  13. #define ull unsigned long long
  14. #define ld long double
  15. #define yes cout << "YES"<<'\n';
  16. #define no cout << "NO"<<'\n';
  17. #define nl "\n"
  18. #define sz(s) (int) (s).size()
  19. #define fr(n) for (int i = 0; i < n; ++i)
  20. #define aw3dni_ink_tet3aleg ios_base::sync_with_stdio(false), cout.tie(NULL), cin.tie(NULL);
  21. // const double PI = 3.14159265358979323846264338327950288419716939937510L;;
  22. #define sp(x) fixed << setprecision(x)
  23. #define all(v) v.begin(), v.end()
  24. #define ff first
  25. #define ss second
  26. #define pii pair<ll,ll>
  27. #define put(x) return void(cout << x)
  28. #define all(v) v.begin(), v.end()
  29. #define allr(v) v.rbegin(), v.rend()
  30. #define cin(vec)                                                                                                       \
  31.     for (auto &i: vec)                                                                                                 \
  32.     cin >> i
  33. #define cout(vec)                                                                                                      \
  34.     for (auto &i: vec)                                                                                                 \
  35.         cout << i << " ";                                                                                              \
  36.     cout << "\n";
  37. #define ON(n, k) ((n) | (1ll << (k)))
  38. #define OFF(n, k) ((n) & ~(1ll << (k)))
  39. #define isON(n, k) (((n) >> (k)) & 1)
  40. #define flip(n, k) ((n) ^ (1ll << (k)))
  41. #define popcnt(x) (__builtin_popcountll(x))
  42.  
  43. template<typename T = int>
  44. istream &operator>>(istream &in, vector<T> &v) {
  45.     for (auto &x: v)in >> x;
  46.     return in;
  47. }
  48.  
  49. template<typename T = int>
  50. ostream &operator<<(ostream &out, const vector<T> &v) {
  51.     for (const T &x: v)out << x << ' ';
  52.     return out;
  53. }
  54.  
  55. void FILES() {
  56.     aw3dni_ink_tet3aleg
  57.     // freopen("angle3.in", "r", stdin);
  58.     // freopen("angle3.out", "w", stdout);
  59. }
  60.  
  61. #define ceil_i(a, b) (((ll) (a) + (ll) (b - 1)) / (ll) (b))
  62. #define floor_i(a, b) (a / b)
  63. #define round_i(a, b) ((a + (b / 2)) / b)
  64.  
  65. ll OO = 1e17, MOD = 1e9 + 7; //1e9 + 7 ,,998244353
  66.  
  67. // int add(int a, int b) { return ((a % MOD) + (b % MOD) + MOD) % MOD; }
  68.  
  69. // int mul(int a, int b) { return (((a % MOD) * (b % MOD))) % MOD; }
  70. int add(int a, int b) {
  71.     if (a < 0)
  72.         a += MOD;
  73.     if (a >= MOD)
  74.         a -= MOD;
  75.     if (b < 0)
  76.         b += MOD;
  77.     if (b >= MOD)
  78.         b -= MOD;
  79.     if (a + b >= MOD)
  80.         return a + b - MOD;
  81.     return a + b;
  82. }
  83.  
  84. // int add(int a, int b) {
  85. //     return (0ll + a + b + MOD) % MOD;
  86. // }
  87. int sub(int a, int b) {
  88.     return add(a, -b);
  89. }
  90.  
  91. int mul(int a, int b) {
  92.     return (1ll * a * b) % MOD;
  93. }
  94.  
  95. // int sub(int a, int b) { return (((a % MOD) - (b % MOD)) + MOD) % MOD; }
  96.  
  97.  
  98. #define INF 1e18
  99.  
  100. int dx[] = {1, 0, -1, 0, -1, -1, 1, 1};
  101. int dy[] = {0, -1, 0, 1, -1, 1, -1, 1};
  102. char di[] = {'D', 'L', 'U', 'R'};
  103. // up right down left
  104.  
  105. const int N = 1e3 + 5, X = 505, EPS = 1e-12;
  106.  
  107. // وَقُلْ رَبِّ زِدْنِي عِلْمًا
  108. // typedef ll T;
  109. // typedef complex<T> pt;
  110. // #define x real()
  111. // #define y imag()
  112. ll fact[N + 1], inv_fact[N + 1];
  113. ll modPow(ll x, ll n, ll mod) {
  114.     x %= mod;
  115.     ll res = 1;
  116.     while (n > 0) {
  117.         if (n % 2) res = res * x % mod;
  118.         x = x * x % mod;
  119.         n /= 2;
  120.     }
  121.     return res;
  122. }
  123.  
  124. int modInverse(int a, int m) {
  125.     /// m==>MOD
  126.     // eq = c*(a^-1)-- c is Numerator --- a is Denominator
  127.     //a==>mod inverse
  128.     // use mull(c,modInvers)
  129.     return modPow(a, m - 2, MOD);
  130. }
  131.  
  132. void factorial() {
  133.     fact[0] = 1;
  134.     for (int i = 1; i <= N; i++) fact[i] = fact[i - 1] * i % MOD;
  135. }
  136.  
  137. void inv_factorial() {
  138.     inv_fact[N] = modPow(fact[N], MOD - 2, MOD);
  139.     for (int i = N; i >= 1; i--) inv_fact[i - 1] = inv_fact[i] * i % MOD;
  140. }
  141.  
  142. ll NCR(ll n, ll r) {
  143.     if (r < 0 || r > n) return 0;
  144.     return fact[n] * inv_fact[r] % MOD * inv_fact[n - r] % MOD;
  145. }
  146.  
  147. void pre_count() {
  148.     factorial();
  149.     inv_factorial();
  150. }
  151. int n , k ;
  152. ll arr[N],dp[N][X];
  153. ll calc(int idx , int rem){
  154.     if(rem<0)
  155.      return 0;
  156.     if(idx==n)
  157.         return rem==0;
  158.     int &ret = dp[idx][rem];
  159.     if(~ret)
  160.      return ret;
  161.     ret = 0;
  162.     for(int i = 0;i<=min(k-1,arr[idx]-1);i++){
  163.         if(rem>=i)
  164.             ret =add(ret,mul(NCR(arr[idx],i),calc(idx+1,rem-i)));
  165.     }
  166.     return ret;
  167. }
  168. void solve() {
  169.     cin >> n >> k ;
  170.     for(int i = 0 ; i<n ; i++){
  171.         cin >>arr[i];
  172.     }
  173.     memset(dp,-1,sizeof(dp));
  174.     ll ans = calc(0,k);
  175.     if(ans > MOD)
  176.         ans-=MOD;
  177.     cout << ans;
  178. }
  179.  
  180.  
  181. signed main() {
  182.     //=========================================================================
  183.     FILES();
  184.     //=========================================================================
  185.     int T = 1, t = 1;
  186.     // phi_1_to_n();
  187.     // linear_sieve(1e6);
  188.     pre_count();
  189.     // sieve();
  190.     // PascalPyramid();
  191.     // computeCatalan();
  192.     // preprocess(50);
  193.     // totient_sieve();
  194.     // cin >> T;
  195.     while (T--) {
  196.         solve();
  197.         t++;
  198.         // vid++;
  199.         cout << nl;
  200.     }
  201.     return 0;
  202. }
  203.  
Success #stdin #stdout 0.01s 7500KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/JmXO0T
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!