Submission #124749

#TimeUsernameProblemLanguageResultExecution timeMemory
124749Mamnoon_SiamBoat (APIO16_boat)C++17
0 / 100
1221 ms16376 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; const int mod = 1e9 + 7; namespace mod_utility { const long long mod = 1e9 + 7; using ll = long long; template <typename dt> inline ll qpow(ll b, dt p) { if(p < 0) return qpow(qpow(b, -p), mod - 2); long long ret = 1; while(p) { if(p & 1) ret = (ret * b) % mod; b = (b * b) % mod, p >>= 1; } return ret; } struct base { using Int = long long; Int x; base() {x = 0;} base(Int _x) { x = _x; if(x < 0 or x >= mod) fix(); } inline void fix() { x %= mod; if(x < 0) x += mod; } template <typename dt> inline base pow(dt p) { return base(qpow(x, p)); } friend ostream& operator << (ostream &out, const base &p) { return out << p.x; } friend istream& operator >> (istream &in, base &p) { return in >> p.x; } inline base operator + (const base &that) const { // assuming both are in [0, mod) return x + that.x >= mod ? base(x + that.x - mod) : base(x + that.x); } inline base operator - (const base &that) const { // assuming both are in [0, mod) return x < that.x ? base(x - that.x + mod) : base(x - that.x); } inline base operator * (const base &that) const { return base(x * that.x); } inline base operator / (const base &that) const { return base(x * qpow(that.x, -1)); } inline void operator += (const base &that) { *this = *this + that; } inline void operator -= (const base &that) { *this = *this - that; } inline void operator *= (const base &that) { *this = *this * that; } inline void operator /= (const base &that) { *this = *this / that; } }; } using namespace mod_utility; const int maxn = 505; base inv[maxn << 1]; base C[maxn][maxn]; base choose(int n, int r) { if(r > n or r < 0 or n < 0) return 0; base ret = 1; for(int i = 1; i <= r; i++, n--) { ret *= inv[i] * n; } return ret; } int n; int a[maxn], b[maxn]; int N_rng; int l[maxn << 1], r[maxn << 1]; base dp[maxn << 1][maxn]; base BC[maxn << 1][maxn]; /* BC = nCr for big N = range size, [range][r] */ base SC[maxn][maxn]; /* SC = nCr for small N, all pair (N, R) */ base g[maxn << 1][maxn]; /* g[range][k] = \sum{i = 1}^{k} \binom{k - 1}{i - 1} * \binom{range_size}{i} */ int main(int argc, char const *argv[]) { cin >> n; vector<int> tmp; for(int i = 1; i <= n; i++) { cin >> a[i] >> b[i]; tmp.emplace_back(a[i]); tmp.emplace_back(b[i]); } sort(tmp.begin(), tmp.end()); tmp.erase(unique(tmp.begin(), tmp.end()), tmp.end()); N_rng = 1; l[1] = r[1] = tmp[0]; for(int i = 1; i < tmp.size(); i++) { N_rng++; l[N_rng] = tmp[i - 1] + 1; r[N_rng] = tmp[i]; } { // precalc factorial^{-1} inv[0] = 1; for(int i = 1; i <= n; i++) { inv[i] = inv[i - 1] / i; } } { // precalc C[][] for(int i = 0; i <= n; i++) { SC[i][0] = 1; } for(int i = 1; i <= n; i++) { for(int j = 1; j <= i; j++) { SC[i][j] = SC[i - 1][j] + SC[i - 1][j - 1]; } } } { // precalc BC[][] for(int i = 1; i <= N_rng; i++) { for(int j = 0; j <= n; j++) { int sz = r[i] - l[i] + 1; if(sz < j) { BC[i][j] = 0; } else { BC[i][j] = 1; for(int k = 1; k <= j; k++, sz--) { BC[i][j] *= inv[k] * sz; } } } } } { // precalc g[][] for(int range = 1; range <= N_rng; range++) { for(int k = 1; k <= n; k++) { for(int i = 1; i <= k; i++) { g[range][k] += SC[k - 1][i - 1] * BC[range][i]; } } } } for(int i = 0; i <= N_rng; i++) { dp[i][0] = 1; } for(int rng = 1; rng <= N_rng; rng++) { for(int i = 1; i <= n; i++) { dp[rng][i] = dp[rng - 1][i]; if(a[i] <= l[rng] and r[rng] <= b[i]) { int cnt = 0; for(int k = i; k >= 1; k--) { if(a[i] <= l[rng] and r[rng] <= b[i]) { cnt++; } dp[rng][i] += dp[rng - 1][k - 1] * g[rng][cnt]; } } } } base ans = 0; for(int i = 1; i <= n; i++) { ans += dp[N_rng][i]; } cout << ans << endl; return 0; }

Compilation message (stderr)

boat.cpp: In function 'int main(int, const char**)':
boat.cpp:78:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 1; i < tmp.size(); i++) {
                 ~~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...