fork download 
  1. /// Author : Nguyễn Thái Sơn - Ti20 - THPT chuyên Lương Thế Vinh
  2.  
  3. #include<bits/stdc++.h>
  4. //#include <ext/pb_ds/assoc_container.hpp>
  5. //#include <ext/pb_ds/trie_policy.hpp>
  6. //#include <ext/rope>
  7.  
  8. //#pragma GCC optimize("Ofast")
  9. //#pragma GCC optimization("unroll-loops, no-stack-protector")
  10. //#pragma GCC target("avx,avx2,fma")
  11.  
  12. //using namespace std;
  13. //using namespace __gnu_pbds;
  14. //using namespace __gnu_cxx;
  15.  
  16. #define fi first
  17. #define se second
  18. #define TASK "test"
  19. #define pb push_back
  20. #define EL cout << endl
  21. #define Ti20_ntson int main()
  22. #define in(x) cout << x << endl
  23. #define all(x) (x).begin(),(x).end()
  24. #define getbit(x, i) (((x) >> (i)) & 1)
  25. #define cntbit(x) __builtin_popcount(x)
  26. #define FOR(i,l,r) for (int i = l; i <= r; i++)
  27. #define FORD(i,l,r) for (int i = l; i >= r; i--)
  28. #define Debug(a,n) for (int i = 1; i <= n; i++) cout << a[i] << " "; cout << endl
  29.  
  30. using namespace std;
  31.  
  32. typedef long long ll;
  33. typedef vector<int> vi;
  34. typedef pair<int,int> vii;
  35. typedef unsigned long long ull;
  36. typedef vector<vector<int>> vvi;
  37.  
  38. const int N = 3005;
  39. const int oo = INT_MAX;
  40. const int mod = 1e9 + 7;
  41. const int d4x[4] = {-1, 0, 1, 0} , d4y[4] = {0, 1, 0, -1};
  42. const int d8x[8] = {-1, -1, 0, 1, 1, 1, 0, -1}, d8y[8] = {0, 1, 1, 1, 0, -1, -1, -1};
  43.  
  44. int n, k, a[N], m = 0;
  45.  
  46. inline void Read_Input() {
  47.     cin >> n >> k;
  48.     FOR(i, 1, n) {
  49.         cin >> a[i];
  50.         a[i] = abs(a[i]);
  51.         m += a[i];
  52.     }
  53. }
  54.  
  55. ll ifact[N + 5], fact[N + 5];
  56.  
  57. inline ll C(int k, int n) {
  58.     if (k > n) return 0;
  59.     return (fact[n] * ifact[n - k] % mod)* ifact[k] % mod;
  60. }
  61.  
  62. long long Pow(int x, int y) {
  63.     if (y == 0) return 1;
  64.     if (y == 1) return x;
  65.     ll res = Pow(x, y / 2);
  66.     res = res * res % mod;
  67.     if (y & 1) return res * x % mod;
  68.     return res;
  69. }
  70.  
  71. long long dp[105][1005];
  72.  
  73. inline void Solve() {
  74.     fact[0] = 1;
  75.     FOR(i, 1, N) fact[i] = fact[i - 1] * i % mod;
  76.     ifact[N] = Pow(fact[N], mod - 2);
  77.     FORD(i, N, 1) ifact[i - 1] = ifact[i] * i % mod;
  78.     dp[0][0] = 1;
  79.  
  80.     /// m = x1 + x2 + ... + x3
  81.  
  82.     for (int i = 1; i <= n; i++)
  83.         for (int j = 0; j <= k; j++) {
  84.                 /// trong do vien bi thu i se co t cap T - P
  85.                 for (int t = 0; t <= j; t++)
  86.                     dp[i][j] = (dp[i][j] + (dp[i - 1][j - t] * C(a[i] + t, a[i] + 2 * t) % mod) * ifact[a[i] + 2 * t] % mod) % mod;
  87.         }
  88.     ll Ans = 0;
  89.  
  90.     for (int i = m; i <= k; i += 2) {
  91.         Ans = (Ans + (dp[n][(i - m) / 2] * C(i, k) % mod) * fact[i] % mod) % mod;
  92.     }
  93.     cout << Ans;
  94. }
  95.  
  96. Ti20_ntson {
  97. //    freopen(TASK".INP","r",stdin);
  98. //    freopen(TASK".OUT","w",stdout);
  99.     ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  100.     int T = 1;
  101.     while (T -- ) {
  102.         Read_Input();
  103.         Solve();
  104.     }
  105. }
  106.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin 
Standard input is empty
stdout 
1
https://ideone.com/0P2hYu
language:
C++14 (gcc 8.3)
created:
14 days 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!