fork download
copy 
  1. //#pragma GCC optimize("O3", "unroll-loops")
  2. //#pragma GCC target("avx2", "bmi", "bmi2", "lzcnt", "popcnt")
  3.  
  4. #include <bits/stdc++.h>
  5. #define ldb long double
  6. //#define double ldb
  7. #define db double
  8. #define unomap unordered_map
  9. #define unoset unordered_set
  10. #define endl '\n'
  11. #define str string
  12. #define strstr stringstream
  13. #define sz(a) (int)a.size()
  14. #define ll long long
  15. //#define int ll
  16. #define pii pair <int, int>
  17. #define pll pair <ll, ll>
  18. #define Unique(a) a.resize(unique(all(a)) - a.begin())
  19. #define ull unsigned ll
  20. #define fir first
  21. #define sec second
  22. #define idc cin.ignore()
  23. #define lb lower_bound
  24. #define ub upper_bound
  25. #define all(s) s.begin(), s.end()
  26. #define rev reverse
  27. #define gcd __gcd
  28. #define pushb push_back
  29. #define popb pop_back
  30. #define pushf push_front
  31. #define popf pop_front
  32. #define mul2x(a, x) a << x
  33. #define div2x(a, x) a >> x
  34. #define lcm(a, b) (a / __gcd(a, b) * b)
  35. #define log_base(x, base) log(x) / log(base)
  36. #define debug cerr << "No errors!"; exit(0);
  37. #define forw(i, a, b)  for (int (i) = (a); (i) <= (b); ++(i))
  38. #define forw2(i, a, b) for (ll (i) = (a); (i) <= (b); ++(i))
  39. #define fors(i, a, b)  for (int (i) = (a); (i) >= (b); --(i))
  40. #define fors2(i, a, b) for (ll (i) = (a); (i) >= (b); --(i))
  41. #define pqueue priority_queue
  42. #define sqrt sqrtl
  43. #define i128 __int128
  44. #define popcount __builtin_popcountll
  45. #define BIT(x, i) (((x) >> (i)) & 1)
  46. #define MASK(x) ((1LL) << (x))
  47. #define want_digit(x) cout << fixed << setprecision(x);
  48. #define excuting_time 1000.0 * clock() / CLOCKS_PER_SEC
  49. #define mapa make_pair
  50. using namespace std;
  51. // const int MOD = 1e9 + 7; // 998244353
  52. const int MOD = 1e6 + 3;
  53. const int inf = 1e9;
  54. const ll INF = 1e18; // MASK(63) - 1
  55. const int N = 4e5;
  56.  
  57. mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
  58. ll random(const ll &L, const ll &R) {
  59.     return uniform_int_distribution<ll> (L, R) (rng);
  60. }
  61.  
  62. void add(int &x, const int &y) {
  63.     x += y;
  64.     if (x >= MOD) x -= MOD;
  65. }
  66.  
  67. const int N4 = 4e3;
  68. int n, a[N + 5], dp[N4 + 5][N4 + 5], lim;
  69. ll m;
  70. void sub4() {
  71.     forw (i, 1, lim + 1) dp[i][i - 1] = 1;
  72.  
  73.     for (int len = 2; len <= lim; len += 2) {
  74.         for (int l = 1; l + len - 1 <= lim; ++l) {
  75.             int r = l + len - 1;
  76.             ll res = 0;
  77.             for (int k = l + 1; k <= r; k += 2) {
  78.                 if ((ll)a[k] - (ll)a[l] > m) break;
  79.                 res += (ll)dp[l + 1][k - 1] * dp[k + 1][r] % MOD;
  80.                 if (res >= MOD) res %= MOD;
  81.             }
  82.             dp[l][r] = res % MOD;
  83.         }
  84.     }
  85.  
  86.     cout << dp[1][lim] % MOD << endl;
  87. }
  88.  
  89. ll mul(const ll &a, const ll &b, const ll &mod) {
  90.     if (!b) return 0;
  91.     if (b == 1) return a % mod;
  92.  
  93.     ll tmp = mul(a, b >> 1, mod);
  94.     (tmp <<= 1) %= mod;
  95.     if (b & 1) (tmp += a % mod) %= mod;
  96.     return tmp;
  97. }
  98.  
  99. ll power_mod(const ll &x, const ll &n, const ll &mod) {
  100.     if (!n) return 1;
  101.     if (n == 1) return x % mod;
  102.     ll X = power_mod(x, n >> 1, mod);
  103.     X = mul(X, X, mod);
  104.     if (n & 1) X = mul(X, x, mod);
  105.     return X;
  106. }
  107.  
  108. ll fact_mod(int x) {
  109.     ll ret = 1;
  110.     forw2 (i, 1, x) (ret *= i) %= MOD;
  111.     return ret;
  112. }
  113.  
  114. ll mod_inv(const ll &a, const ll &m) {
  115.     return power_mod(a, m - 2, m) % m;
  116. }
  117.  
  118. ll mod_div(const ll &a, const ll &b, const ll &mod) {
  119.     ll inv = mod_inv(b, mod);
  120.     return mul(a, inv, mod);
  121. }
  122.  
  123. ll catalan_mod(int n) {
  124.     ll num = fact_mod(n * 2);
  125.     ll den = mul(fact_mod(n + 1), fact_mod(n), MOD);
  126.     ll res = mod_div(num, den, MOD);
  127.     return res;
  128. }
  129.  
  130. void sub5() {
  131.     cout << catalan_mod(n) << endl;
  132. }
  133.  
  134. void solve() {
  135.     cin >> n >> m;
  136.     lim = n * 2;
  137.     forw (i, 1, lim) cin >> a[i];
  138.  
  139.     if (n <= 2e3) sub4();
  140.     else sub5();
  141. }
  142.  
  143. signed main() {
  144.     ios::sync_with_stdio(false), cin.tie(nullptr);
  145.     srand(time(NULL));
  146.     #define name "test"
  147.     /*
  148.     if (fopen(name".INP", "r")) {
  149.         freopen(name".INP", "r", stdin);
  150.         freopen(name".OUT", "w", stdout);
  151.     }
  152.     */
  153.     bool testCase = false;
  154.     int numTest = 1;
  155. //    cin >> numTest;
  156.     forw (i, 1, numTest) {
  157.         if (testCase) cout << "Case " << i << ": ";
  158.         solve();
  159.     }
  160.     return 0;
  161. }
  162.  
Success #stdin #stdout 0.01s 5728KB
comments (?)
stdin
copy 
3 6
1 2 3 7 9 10
stdout
copy 
2
https://ideone.com/Rp6Nqc
language:
C++14 (gcc 8.3)
created:
24 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!