QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#792667#4564. Digital Circuit_8_8_#2 13ms6172kbC++231.5kb2024-11-29 12:46:452024-11-29 12:46:46

Judging History

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

  • [2024-11-29 12:46:46]
  • 评测
  • 测评结果:2
  • 用时:13ms
  • 内存:6172kb
  • [2024-11-29 12:46:45]
  • 提交

answer

#include "circuit.h"

#include <bits/stdc++.h>

using namespace std;
const int N = (int)1e5 + 12, MOD = 1000002022;

typedef long long ll;
#define int ll
int n, m, f, a[N];
vector<int> g[N], dp[N];
void add(int &x, int y) {
    x += y;
    if(x >= MOD) x -= MOD;
}
int pd[N][2];
void dfs(int v) {
    if(v >= n) {
        pd[v][a[v]] = 1;
        pd[v][1 - a[v]] = 0;
        return;
    }
    int sz = (int)g[v].size();
    for(int i = 1; i <= sz; i++) {
        dp[v][i] = 0;
    }
    dp[v][0] = 1;
    for(int to : g[v]) {
        dfs(to);
        int x = pd[to][1], y = pd[to][0];
        for(int i = sz; i >= 0; i--) {
            dp[v][i] = (dp[v][i] * 1ll * y) % MOD;
            if(i) add(dp[v][i], dp[v][i - 1] * 1ll * x % MOD);
        }
    }
    pd[v][0] = dp[v][0];
    pd[v][1] = 0;   
    for(int i = 1; i <= sz; i++) {
        add(pd[v][1], dp[v][i] * 1ll * (i) % MOD);
        add(pd[v][0], dp[v][i] * 1ll * (sz - i) % MOD);
    }
}
void init(int32_t NN, int32_t MM, std::vector<int32_t> P, std::vector<int32_t> A) {
    n = NN;
    m = MM;
    f = n + m;
    for(int i = n; i < f; i++) {
        a[i] = A[i - n];
    }
    for(int i = 1; i < f; i++) {
        g[P[i]].push_back(i);
    }

    for(int i = 0; i < f; i++) {
        dp[i].resize((int)g[i].size() + 1);
    }
}

int32_t count_ways(int32_t L, int32_t R) {
    for(int i = L; i <= R; i++) {
        a[i] ^= 1;
    }
    dfs(0);
    assert(pd[0][1] >= 0);
    return pd[0][1];
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 2
Accepted

Test #1:

score: 2
Accepted
time: 1ms
memory: 3836kb

input:

1 2
-1 0 0
0 0
1 1
2 2
1 2
2 2
1 2
-1 -1
-2 -2

output:

1
2
0
1
1

result:

ok 7 lines

Test #2:

score: 2
Accepted
time: 0ms
memory: 3776kb

input:

1 1
-1 0
0
1 1
1 1
1 1
1 1
-1 -1
-2 -2

output:

1
0
1
0

result:

ok 6 lines

Test #3:

score: 2
Accepted
time: 12ms
memory: 3804kb

input:

1 972
-1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0...

output:

509
483
489
500
481

result:

ok 7 lines

Test #4:

score: 2
Accepted
time: 9ms
memory: 3808kb

input:

1 1000
-1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

output:

4
40
428
262
237

result:

ok 7 lines

Test #5:

score: 2
Accepted
time: 9ms
memory: 5924kb

input:

1 1000
-1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

output:

898
828
828
617
582

result:

ok 7 lines

Test #6:

score: 2
Accepted
time: 13ms
memory: 6172kb

input:

1 1000
-1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

output:

535
494
500
498
509

result:

ok 7 lines

Test #7:

score: 2
Accepted
time: 13ms
memory: 5932kb

input:

1 1000
-1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

output:

517
486
511
487
512

result:

ok 7 lines

Test #8:

score: 2
Accepted
time: 12ms
memory: 3844kb

input:

1 1000
-1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

output:

501
500
499
500
501

result:

ok 7 lines

Subtask #2:

score: 0
Wrong Answer

Test #9:

score: 7
Accepted
time: 1ms
memory: 3836kb

input:

1 2
-1 0 0
0 0
1 1
2 2
1 2
2 2
1 2
-1 -1
-2 -2

output:

1
2
0
1
1

result:

ok 7 lines

Test #10:

score: 0
Wrong Answer
time: 1ms
memory: 3832kb

input:

255 256
-1 0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 ...

output:

235614624
106164788
545502954

result:

wrong answer 3rd lines differ - expected: '52130940', found: '235614624'

Subtask #3:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

0%

Subtask #4:

score: 0
Time Limit Exceeded

Test #43:

score: 0
Time Limit Exceeded

input:

32767 32768
-1 0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50...

output:

128974656
194451974
572626624
291950370
319851290
260696674
176787396
134891530
378362462
699156588
328892212
724242342
315025656
413036986
530713330
329320610
378374346
659065646
653558604
580081086
460688622
156526264
550307504
583402606
629883910
135252858
751610318
728090550
21810352
344538372
5...

result:


Subtask #5:

score: 0
Skipped

Dependency #4:

0%

Subtask #6:

score: 0
Skipped

Dependency #2:

0%

Subtask #7:

score: 0
Skipped

Dependency #3:

0%

Subtask #8:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

0%