QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#764582 | #8527. Power Divisions | IllusionaryDominance | WA | 292ms | 30424kb | C++20 | 2.4kb | 2024-11-20 09:49:33 | 2024-11-20 09:49:41 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 300000 + 5;
const int MAX_M = 1 << 20;
const ll P = 3270674594228402513ll;
const int MOD = 1000000000 + 7;
mt19937_64 rnd64(chrono::steady_clock::now().time_since_epoch().count());
ll coef[MAX_M], sumc[MAX_M];
inline ll add(ll a, ll b) {return a + b < P ? a + b : a + b - P;}
void init() {
uniform_int_distribution <ll> rndP(1, P - 1);
for (int i = 0; i < MAX_M; i ++) {
coef[i] = rndP(rnd64);
sumc[i] = add(i > 0 ? sumc[i - 1] : 0ll, coef[i]);
}
}
int N, a[MAX_N], f[MAX_N];
vector <int> lp[MAX_N];
void solve(int l, int r) {
if (l == r) {
lp[l].emplace_back(l);
return ;
}
int mid = l + r >> 1;
solve(l, mid); solve(mid + 1, r);
set <int> s;
map <int, int> pre, suf;
ll hash = 0;
auto ins = [&](int x) -> void {
while (s.count(x)) {
hash = add(hash, P - coef[x]);
s.erase(x); x ++;
}
s.insert(x);
hash = add(hash, coef[x]);
};
for (int i = mid; i >= l; i --) {
ins(a[i]);
pre[hash] = i;
}
s.clear(); hash = 0;
for (int i = mid + 1; i <= r; i ++) {
ins(a[i]);
suf[hash] = i;
int lowbit = *s.begin(), highbit = *s.rbegin();
ll tmp = add(sumc[highbit], P - sumc[lowbit]);
tmp = add(tmp, P - hash);
tmp = add(tmp, coef[lowbit]);
tmp = add(tmp, coef[lowbit]);
if (pre.count(tmp)) {
lp[i].emplace_back(pre[tmp]);
}
}
s.clear(); hash = 0;
for (int i = mid; i >= l; i --) {
ins(a[i]);
int lowbit = *s.begin(), highbit = *s.rbegin();
ll tmp = add(sumc[highbit], P - sumc[lowbit]);
tmp = add(tmp, P - hash);
tmp = add(tmp, coef[lowbit]);
tmp = add(tmp, coef[lowbit]);
if (tmp != hash && suf.count(tmp)) {
lp[suf[tmp]].emplace_back(i);
}
}
}
int main() {
init();
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> N;
for (int i = 1; i <= N; i ++) {
cin >> a[i];
}
solve(1, N);
f[0] = 1;
for (int i = 1; i <= N; i ++) {
for (auto j : lp[i]) {
f[i] += f[j - 1];
(f[i] >= MOD && (f[i] -= MOD));
}
}
cout << f[N] << '\n';
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 11ms
memory: 23440kb
input:
5 2 0 0 1 1
output:
6
result:
ok 1 number(s): "6"
Test #2:
score: 0
Accepted
time: 14ms
memory: 22568kb
input:
1 0
output:
1
result:
ok 1 number(s): "1"
Test #3:
score: 0
Accepted
time: 14ms
memory: 24308kb
input:
2 1 1
output:
2
result:
ok 1 number(s): "2"
Test #4:
score: 0
Accepted
time: 7ms
memory: 24156kb
input:
3 2 1 1
output:
3
result:
ok 1 number(s): "3"
Test #5:
score: 0
Accepted
time: 11ms
memory: 22964kb
input:
4 3 2 2 3
output:
4
result:
ok 1 number(s): "4"
Test #6:
score: 0
Accepted
time: 14ms
memory: 22516kb
input:
5 3 4 4 2 4
output:
2
result:
ok 1 number(s): "2"
Test #7:
score: 0
Accepted
time: 11ms
memory: 24136kb
input:
7 3 4 3 5 6 3 4
output:
6
result:
ok 1 number(s): "6"
Test #8:
score: 0
Accepted
time: 14ms
memory: 22676kb
input:
10 8 6 5 6 7 8 6 8 9 9
output:
4
result:
ok 1 number(s): "4"
Test #9:
score: 0
Accepted
time: 7ms
memory: 22728kb
input:
96 5 1 0 2 5 5 2 4 2 4 4 2 3 4 0 2 1 4 3 1 2 0 2 2 3 2 4 5 3 5 2 0 2 2 5 3 0 4 5 3 5 4 4 3 1 2 0 5 4 5 0 2 3 2 4 0 0 4 2 0 2 5 3 3 1 5 5 1 1 1 0 5 0 3 0 2 1 1 0 5 0 3 3 4 4 5 3 0 2 2 0 5 4 5 0 5
output:
11332014
result:
ok 1 number(s): "11332014"
Test #10:
score: 0
Accepted
time: 12ms
memory: 23632kb
input:
480 2 0 4 4 1 0 0 3 1 1 4 2 5 5 4 2 1 2 4 4 1 3 4 3 0 5 2 0 2 5 1 0 5 0 0 5 5 0 2 5 2 2 3 1 4 3 5 4 5 2 4 4 4 4 1 4 0 3 4 3 4 1 0 4 3 4 5 4 3 5 0 2 2 0 1 5 4 4 2 0 3 3 3 4 3 0 5 5 3 1 5 1 0 1 0 4 3 0 5 1 4 1 4 3 0 1 3 5 0 3 3 1 0 4 1 1 2 0 1 2 0 3 5 2 0 5 5 5 5 3 5 1 0 2 5 2 2 0 2 0 2 3 5 1 2 1 5 4 ...
output:
506782981
result:
ok 1 number(s): "506782981"
Test #11:
score: 0
Accepted
time: 18ms
memory: 22616kb
input:
2400 0 2 2 0 5 4 3 2 3 2 5 4 5 4 4 5 2 2 4 2 2 0 1 0 5 0 4 4 0 0 5 0 4 0 1 3 4 5 0 3 1 0 4 0 2 5 0 3 3 3 3 1 0 5 5 3 1 3 5 2 4 0 5 0 4 5 4 2 2 1 5 2 2 4 1 0 5 1 5 0 1 2 0 0 3 5 4 0 0 1 1 1 4 2 0 5 1 3 3 5 0 4 4 1 5 5 3 4 4 4 0 2 4 0 5 1 3 1 5 0 5 5 1 3 0 3 1 2 0 1 1 3 5 2 3 4 0 3 0 5 4 0 4 3 5 0 5 2...
output:
586570528
result:
ok 1 number(s): "586570528"
Test #12:
score: 0
Accepted
time: 58ms
memory: 24328kb
input:
12000 2 2 1 2 0 2 5 3 2 0 1 3 2 5 4 0 0 5 3 2 0 2 3 4 3 2 1 4 3 0 3 5 4 1 0 2 4 1 3 2 3 5 0 3 0 0 4 0 4 5 1 0 4 1 1 1 5 4 3 0 3 5 4 5 2 5 0 1 2 3 5 5 2 5 4 2 0 4 4 3 0 0 2 5 0 3 4 2 5 4 2 1 4 5 1 1 2 3 0 3 3 3 3 4 0 5 3 4 0 3 0 2 0 0 2 0 3 4 2 2 0 1 0 5 3 0 2 0 2 2 1 0 5 3 5 4 5 5 0 4 0 4 1 4 4 3 2 ...
output:
201653965
result:
ok 1 number(s): "201653965"
Test #13:
score: -100
Wrong Answer
time: 292ms
memory: 30424kb
input:
60000 2 5 0 3 2 3 5 3 5 5 4 1 1 5 3 0 1 1 2 5 5 5 0 3 2 0 3 2 3 3 0 0 1 4 3 1 4 2 3 3 0 5 1 0 1 1 5 5 4 0 5 4 1 3 1 3 5 3 2 4 4 4 5 4 3 2 3 2 4 5 2 0 4 5 1 2 0 4 0 5 1 3 4 1 2 4 1 1 3 3 0 1 1 3 0 0 2 3 3 2 1 4 1 2 4 3 3 5 2 5 3 4 3 0 2 1 1 1 5 1 2 4 2 3 1 2 1 0 2 0 1 1 5 5 3 4 2 5 2 4 5 3 0 5 1 4 2 ...
output:
618434569
result:
wrong answer 1st numbers differ - expected: '592751350', found: '618434569'