제출 #1252842

#제출 시각아이디문제언어결과실행 시간메모리
1252842kunzaZa183Boat (APIO16_boat)C++20
0 / 100
1 ms320 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; ll MOD = 1e9 + 7; const int mn = 1500; ll logpow(int a, int b) { if (b == 0) return 1; if (b == 1) return a; ll x = logpow(a, b / 2); if (b % 2 == 1) return x * x % MOD * a % MOD; return x * x % MOD; } vector<ll> fac; ll choose(int n, int r) { if (n < r) return 0; return fac[n] * logpow(fac[r], MOD - 2) % MOD * logpow(fac[n - r], MOD - 2) % MOD; } int main() { int n; cin >> n; vector<pair<int, int>> vpii(n); for (auto &a : vpii) cin >> a.first >> a.second; fac = vector<ll>(mn); fac[0] = 1; for (int i = 1; i < mn; i++) fac[i] = fac[i - 1] * i % MOD; set<int> si; for (auto [a, b] : vpii) si.insert(a), si.insert(b + 1); vector<ll> sth; for (auto a : si) { sth.push_back(a); } vector<vector<array<ll, 3>>> vvi; // surplus, stage, multi vvi.emplace_back(si.size()); for (int i = 0; i < n; i++) { ll cur = 1; for (int j = 0; j + 1 < sth.size(); j++) { auto &[plus, stage, multi] = vvi[i][j]; ll befcur = cur; cur += plus * (sth[j + 1] - sth[j]) % MOD; cur %= MOD; cur += choose((sth[j + 1] - sth[j]) + stage, stage + 1) * multi % MOD; cur %= MOD; if (sth[j] >= vpii[i].first && sth[j] <= vpii[i].second) { if (stage == 0 && multi == 0) { multi = befcur; stage = 0; } else { plus += befcur; plus %= MOD; stage++; } } } vvi.push_back(vvi.back()); } ll ans = 0; for (int j = 0; j + 1 < sth.size(); j++) { auto &[plus, stage, multi] = vvi.back()[j]; ans += plus * (sth[j + 1] - sth[j]) % MOD; ans %= MOD; ans += choose((sth[j + 1] - sth[j]) + stage, stage + 1) * multi % MOD; ans %= MOD; } cout << ans << "\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...