Submission #939726

#TimeUsernameProblemLanguageResultExecution timeMemory
939726sysiaBoat (APIO16_boat)C++17
100 / 100
1644 ms16932 KiB
//Sylwia Sapkowska #include <bits/stdc++.h> #pragma GCC optimize("O3", "unroll-loops") using namespace std; void __print(int x) {cerr << x;} void __print(long long x) {cerr << x;} void __print(long double x) {cerr << x;} void __print(char x) {cerr << "'" << x << "'";} void __print(const char *x) {cerr << '"' << x << '"';} void __print(const string &x) {cerr << '"' << x << '"';} void __print(bool x) {cerr << (x ? "true" : "false");} template<typename T, typename V> void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}';} template<typename T> void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}";} void _print() {cerr << "]\n";} template <typename T, typename... V> void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);} #ifdef LOCAL #define debug(x...) cerr << "[" << #x << "] = ["; _print(x) #else #define debug(x...) #endif #define int long long typedef pair<int, int> T; const int oo = 1e18, oo2 = 1e9+7; const int mod = 1e9+7; int mul(int a, int b){ return (a*b)%mod; } void add(int &a, int b){ a += b; if (a >= mod) a-=mod; } int power(int a, int b){ if (!b) return 1ll; int k = power(a, b/2); k = mul(k, k); if (b&1) k = mul(k, a); return k; } void solve(){ int n; cin >> n; vector<int>a(n+1), b(n+1); vector<int>s = {0, 1}; for (int i = 1; i<=n; i++) { cin >> a[i] >> b[i]; s.emplace_back(a[i]); s.emplace_back(b[i]); } sort(s.begin(), s.end()); s.erase(unique(s.begin(), s.end()), s.end()); debug(s); vector<T>seg; for (int i = 0; i<(int)s.size()-1; i++){ seg.emplace_back(s[i], s[i]); if (s[i]+1 <= s[i+1]-1) seg.emplace_back(s[i]+1, s[i+1]-1); } seg.emplace_back(s.back(), s.back()); debug(seg); vector<int>inv(n+1, 1); for (int i = 1; i<=n; i++){ inv[i] = power(i, mod-2); } // auto nck = [&](int N, int K){ // if (N < 0 || K < 0 || N < K) return 0ll; // return mul(f[N], mul(inv[K], inv[N-K])); // }; int m = (int)seg.size(); //len choose k moze byc bardzo dlugie, ale na szczescie dlugosci len jest O(n), wartosci k jest O(n) //i mozna uzyc lepszego wzorku by to spreprocessowac // vector nck(m, vector<int>(n+1, 1)), I(m, vector<int>(n+1)); // for (int j = 0; j<m; j++){ // int len = seg[j].second - seg[j].first+1; // for (int k = 0; k<=n; k++){ // for (int rep = 0, val = len; rep < k; rep++, val--){ // nck[j][k] = mul(nck[j][k], val); // } // nck[j][k] = mul(nck[j][k], inv[k]); // I[j][k] = power(nck[j][k], mod-2); // } // } //dp[i][j][k] = na ile sposobow da sie wybrac dzialajace rozwiazanie na prefiksie i, gdzie //ostatnie k elementow nalezy do przedzialu seg[j] vector dp(m, vector<int>(n+1, 0)); dp[0][1] = 1; //zerowy przedzial for (int i = 1; i<=n; i++){ auto new_dp = dp; vector<int>pref(m); for (int s = 0; s < m; s++){ if (s) pref[s] += pref[s-1]; for (int k = 0; k <= n; k++) add(pref[s], dp[s][k]); } // dp[i] = dp[i-1]; //nic nie dokladamy for (int j = 1; j<m; j++){ if (seg[j].second < a[i] || seg[j].first > b[i]) continue; int len = seg[j].second - seg[j].first + 1; // dp[i][j][1] = suma po dp[i-1][<j][cokolwiek] add(new_dp[j][1], mul(pref[j-1], len)); //dokladamy pierwszy element tego przedzialu // for (int s = 0; s < j; s++){ // for (int k = 0; k <= n; k++){ // if (dp[i-1][s][k]){ // debug(dp[i-1][s][k], len); // } // add(dp[i][j][1], mul(dp[i-1][s][k], len)); // } // } for (int k = 2; k <= min(i, len); k++){ //dokladamy juz nie pierwszy element tego przedzialu // add(new_dp[j][k], mul(dp[j][k-1], mul(power(nck(len, k-1), mod-2), nck(len, k)))); // add(new_dp[j][k], mul(dp[j][k-1], mul(I[j][k-1], nck[j][k]))); add(new_dp[j][k], mul(dp[j][k-1], mul(len-k+1, inv[k]))); } } dp.swap(new_dp); } int ans = mod-1; for (int i = 0; i<m; i++){ for (int j = 0; j<=n; j++){ add(ans, dp[i][j]); } } cout << ans << "\n"; } int32_t main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t = 1; //cin >> t; while (t--) solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...