#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<cassert>
#include<unordered_map>
#include <queue>
#include <cstdint>
#include<cstring>
#include<limits.h>
#include<cmath>
#include<set>
#include<algorithm>
#include <iomanip>
#include<numeric>
#include<bitset>
using namespace std;
#define ll long long
#define f first
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define vi vector<int>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC optimize ("03,unroll-lopps")
#define int long long
using namespace std;
const int mod=1e9+7,mxn=1e5+5,inf=1e9,minf=-1e18,lg=30,valbound=1e9;
//#undef int
int k,m,q,p,h,w,n;
void setIO(string name){
ios_base::sync_with_stdio(0); cin.tie(0);
freopen((name+".in").c_str(),"r",stdin);
freopen((name+".out").c_str(),"w",stdout);
}
int val[mxn+10];
map<int,int>on;
void simplify(){
bool yes=1;
int cnt=0;
while(yes){
cnt++;
vector<int>del;
for(auto &i:on){
if(i.s==0)continue;
if(i.s>1&&i.f>2){
if(i.s/2){
on[i.f+1]+=(i.s)/2;
on[i.f-2]+=(i.s)/2;
}
i.s%=2;
if(i.s==0)del.pb(i.f);
}
}
for(auto &i:on){
if(i.s==0)continue;
if(i.f==1){
if(i.s/2)on[2]+=(i.s/2);
i.s%=2;
if(i.s==0)del.pb(i.f);
}
else{
int x=min(on[i.f-1],i.s);
if(x){
on[i.f+1]+=x;
i.s-=x;
on[i.f-1]-=x;
}
if(on[i.f-1]==0)del.pb(i.f-1);
if(i.s==0)del.pb(i.f);
}
}
sort(all(del));
del.erase(unique(all(del)),del.end());
for(auto i:del)on.erase(i);
bool nxt=0;
for(auto i:on)if(i.s>1)nxt=1;
yes=nxt;
}
}
int dp[2];
int cal(int a,int b){return ((b-a-1)/2);}
int get(){
int last=-1;
dp[0]=0,dp[1]=0;
for(auto i:on){
if(last==-1){
dp[0]=1;
dp[1]=cal(0,i.f);
}
else{
int x=(dp[0]+dp[1])%mod,y=0;
y=(dp[0]*cal(last,i.f))%mod;
y=(y+(dp[1]*cal(last-1,i.f))%mod)%mod;
dp[0]=x,dp[1]=y;
}
last=i.f;
}
return (dp[0]+dp[1])%mod;
}
int32_t main(){
fastio
int n;cin>>n;
for(int i=1;i<=n;i++)cin>>val[i];
for(int i=1;i<=n;i++){
on[val[i]]++;
simplify();
cout<<get()<<'\n';
}
}
/*
for a number x with occurences y
we can make the number x+z using fib(z+1) xs
we can push the number and get a set of number with only 1 occurence
what to do with these distinct number?
for a number x
we can split it into x-1,x-2
if we keep spliting to x-1,x-3,x-4
x-1,x-3,x-5,x-6
we can see the odd number wont be able to split as it will result in having the same number
so there has to be an even number y that is the end
we can do dp[i][split?]
dp[i][not split]=(sum of dp[i-1])
dp[i][split]={
dp[i-1][not split]*(number of usable y in range (val[i-1],val[i]))
+
dp[i-1][split]*(number of usable y in range (val[i-1]-1,val[i]))
}
would this work?
*/
Compilation message
fib.cpp:32:40: warning: bad option '-funroll-lopps' to pragma 'optimize' [-Wpragmas]
32 | #pragma GCC optimize ("03,unroll-lopps")
| ^
fib.cpp:38:23: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
38 | void setIO(string name){
| ^
fib.cpp:45:15: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
45 | void simplify(){
| ^
fib.cpp:90:20: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
90 | int cal(int a,int b){return ((b-a-1)/2);}
| ^
fib.cpp:91:9: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
91 | int get(){
| ^
fib.cpp:109:14: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
109 | int32_t main(){
| ^
fib.cpp: In function 'void setIO(std::string)':
fib.cpp:40:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
40 | freopen((name+".in").c_str(),"r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fib.cpp:41:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
41 | freopen((name+".out").c_str(),"w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
468 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
344 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
468 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
344 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Execution timed out |
4073 ms |
348 KB |
Time limit exceeded |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
468 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
344 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Execution timed out |
4073 ms |
348 KB |
Time limit exceeded |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Execution timed out |
4089 ms |
2992 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
468 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
344 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Execution timed out |
4073 ms |
348 KB |
Time limit exceeded |
| 8 |
Halted |
0 ms |
0 KB |
- |
