Submission #480808

#TimeUsernameProblemLanguageResultExecution timeMemory
480808wiwihoFibonacci representations (CEOI18_fib)C++14
0 / 100
7 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; b >>= 1; } return ans; } ll solve(vector<int> a){ lsort(a); vector<int> cnt(501); for(int i : a) cnt[i]++; cnt[2] += cnt[1] / 2; cnt[1] %= 2; for(int j = 1; j <= 500; j++){ for(int i = 498; i >= 1; i--){ int t = min(cnt[i], cnt[i + 1]); cnt[i] -= t; cnt[i + 1] -= t; cnt[i + 2] += t; } for(int i = 500; i - 2 >= 1; i--){ if(cnt[i] > 2) return 0; if(cnt[i] <= 1) continue; cnt[i - 1]++; cnt[i - 2]++; cnt[i] = 1; } } if(cnt[1] > 1 || cnt[2] > 1) return 0; //for(int i = 1; i <= 20; i++) cerr << cnt[i] << " "; //cerr << "\n"; vector<int> dp(501); dp[0] = 1; for(int i = 499; i >= 0; i--){ for(int j = i + 1; j <= 500; j++){ if(i % 2 != j % 2){ if(cnt[i + 1] == 0 || j == i + 1) dp[0] += dp[j]; dp[0] %= MOD; if(cnt[i] == 1) dp[j] = 0; } } if(cnt[i] == 1){ dp[i] = dp[0]; dp[0] = 0; } //if(i > 20) continue; //cerr << "dp " << i << " "; //for(int j = 0; j <= 20; j++) cerr << dp[j] << " "; //cerr << "\n"; } return dp[0]; } int main(){ ios_base::sync_with_stdio(false); cin.tie(0); int n; cin >> n; assert(n <= 100); vector<int> a; for(int i = 0; i < n; i++){ int x; cin >> x; assert(x <= 100); a.eb(x); cout << solve(a) << "\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...