QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#764582#8527. Power DivisionsIllusionaryDominanceWA 292ms30424kbC++202.4kb2024-11-20 09:49:332024-11-20 09:49:41

Judging History

你现在查看的是最新测评结果

  • [2024-11-20 09:49:41]
  • 评测
  • 测评结果:WA
  • 用时:292ms
  • 内存:30424kb
  • [2024-11-20 09:49:33]
  • 提交

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'