#include <bits/stdc++.h>
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define sorv(V) sort(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define upmin(a,b) (a)=min((a),(b))
#define INF (0x3f3f3f3f)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MOD = 1000000007;
bitset<5555> A;
int N;
void push(int X) {
if(X < 1) return;
if(1 == X) X = 2;
if(!A[X]) {
A[X] = true;
if(A[X-1]) {
A[X-1] = A[X] = false;
push(X+1);
return;
}
for(int i = X; A[i] && A[i+1];) {
A[i] = A[i+1] = false;
i += 2;
A[i] = true;
}
return;
}
int s = X, e = X;
for(; 0 <= s-2 && A[s-2]; s -= 2);
for(; A[e+2]; e += 2);
for(int i = s; i <= e; i++) A[i] = false;
for(int i = s+1; i < X; i += 2) A[i] = true;
push(e+1);
push(s-2);
}
ll getAns() {
vector<pii> V;
for(int i = 1; i < 5000; i++) if(A[i]) {
int j = i; for(; A[j+2]; j += 2);
V.eb(i, j);
i = j;
}
//for(auto &v : V) printf("(%d,%d) ", v.first, v.second); puts("");
vector<ll> DP[2];
int N = sz(V);
DP[0].resize(N); DP[1].resize(N);
if(1 < V[0].first-2) {
DP[0][0] = ll(V[0].first-4)/2 % MOD + 1;
}
DP[1][0] = 1 + ll(V[0].first-2)/2 * ((V[0].second-V[0].first)/2) % MOD;
for(int i = 1; i < N; i++) {
int l = V[i].first - V[i-1].second - 1;
int c = (V[i].second - V[i].first)/2;
DP[0][i] = (DP[1][i-1] * (l/2) % MOD) + (DP[0][i-1] * ((l+1)/2) % MOD);
DP[0][i] %= MOD;
DP[1][i] = 1 + (DP[1][i-1] * (l/2) % MOD * c % MOD);
DP[1][i] += DP[0][i-1] * ((l+1)/2) % MOD * c % MOD;
DP[1][i] %= MOD;
}
//for(int i = 0; i < N; i++) printf("DP %d : %lld %lld\n", i, DP[0][i], DP[1][i]);
return (DP[0].back() + DP[1].back()) % MOD;
}
int main() {
cin >> N;
for(int i = 0; i < N; i++) {
int x;
cin >> x;
push(x+1);
cout << getAns() << endl;
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
504 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
