Submission #480802

#TimeUsernameProblemLanguageResultExecution timeMemory
480802wiwihoFibonacci representations (CEOI18_fib)C++14
0 / 100
4051 ms460 KiB
#include<bits/stdc++.h> #define eb emplace_back #define iter(a) a.begin(), a.end() #define lsort(a) sort(iter(a)) #define uni(a) a.resize(unique(iter(a)) - a.begin()) #define printv(a, b) {\ for(auto pv : a) b << pv << " ";\ b << "\n";\ } using namespace std; typedef long long ll; ll MOD = 1000000007; ll inv(ll a){ ll b = MOD - 2; ll ans = 1; while(b > 0){ if(b & 1) ans = ans * a % MOD; a = a * a % MOD; } return ans; } int calc(int a, int b){ return (b - a) / 2; } int main(){ ios_base::sync_with_stdio(false); cin.tie(0); int n; cin >> n; set<int> a; a.insert(0); ll ans = 1; for(int i = 0; i < n; i++){ int x; cin >> x; assert(x % 2 == 0 && a.find(x) == a.end()); auto it = a.lower_bound(x); if(it != a.end()){ ans = ans * inv(calc(*prev(it), *it)) % MOD; ans = ans * calc(x, *it) % MOD; } ans = ans * calc(*prev(it), x) % MOD; a.insert(x); cout << ans << "\n"; } 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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...