QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#191444#5487. Movie Nightyaroslav06WA 56ms9496kbC++141.4kb2023-09-29 23:09:002023-09-29 23:09:00

Judging History

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

  • [2023-09-29 23:09:00]
  • 评测
  • 测评结果:WA
  • 用时:56ms
  • 内存:9496kb
  • [2023-09-29 23:09:00]
  • 提交

answer

#include <bits/stdc++.h>

const int N = 1e5;

int mod = 1e9 + 7;

using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
template<class T>bool umin(T& a,const T& b){return b<a ? a=b,1:0;}
template<class T>bool umax(T& a,const T& b){return a<b ? a=b,1:0;}

int t[N], r[N]{}, vs[N];
bool usd[N]{};

int qpow(ll a, int b){
    ll rs = 1;
    while(b){
        if(a&1) rs *= a, rs %= mod;
        a *= a;
        a %= mod;
    }
    return rs;
}

ll dfs(int i, int st){
    usd[i] = 1;
    if(i == st) return vs[i];
    return vs[i] * dfs(t[i], st) % mod;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    for(int i = 0; i < n; ++i)
        vs[i] = 1;
    for(int i = 0; i < n; ++i)
        cin >> t[i], --t[i], ++r[t[i]];
    set<pair<int, int>> s;
    for(int i = 0; i < n; ++i)
        s.insert({r[i], i});
    while(!s.empty() and s.begin() -> first == 0){
        int v = s.begin() -> second;
        s.erase(s.begin());
        usd[v] = 1;
        s.erase({r[t[v]], t[v]});
        --r[t[v]];
        s.insert({r[t[v]], t[v]});
        int u = t[v];
        vs[u] *= vs[v] + 1;
        vs[u] %= mod;
    }
    ll rs = 1;
    for(int i = 0, u; i < n; ++i) if(!usd[i])
        u = dfs(t[i], i),
        rs *= u + 1, rs %= mod;
    cout << (rs - 1 + mod) % mod << endl;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3504kb

input:

4
2
3
4
3

output:

3

result:

ok single line: '3'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3512kb

input:

5
2
3
1
5
4

output:

3

result:

ok single line: '3'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3824kb

input:

6
2
4
2
6
1
3

output:

3

result:

ok single line: '3'

Test #4:

score: 0
Accepted
time: 0ms
memory: 3644kb

input:

8
2
3
4
1
3
3
1
4

output:

16

result:

ok single line: '16'

Test #5:

score: 0
Accepted
time: 0ms
memory: 3508kb

input:

4
3
3
4
3

output:

4

result:

ok single line: '4'

Test #6:

score: 0
Accepted
time: 0ms
memory: 3564kb

input:

8
8
6
8
1
3
3
3
6

output:

24

result:

ok single line: '24'

Test #7:

score: 0
Accepted
time: 0ms
memory: 3600kb

input:

8
6
6
6
1
8
7
1
7

output:

24

result:

ok single line: '24'

Test #8:

score: 0
Accepted
time: 0ms
memory: 3624kb

input:

7
2
3
1
5
4
7
6

output:

7

result:

ok single line: '7'

Test #9:

score: 0
Accepted
time: 0ms
memory: 3632kb

input:

11
2
5
2
2
6
7
5
5
10
11
10

output:

56

result:

ok single line: '56'

Test #10:

score: 0
Accepted
time: 0ms
memory: 3628kb

input:

30
11
27
25
25
18
18
4
9
27
30
7
16
22
22
28
11
4
30
6
7
13
9
29
26
16
29
28
13
6
26

output:

35936

result:

ok single line: '35936'

Test #11:

score: 0
Accepted
time: 0ms
memory: 3640kb

input:

192
2
3
2
5
6
5
8
9
8
11
12
11
14
15
14
17
18
17
20
21
20
23
24
23
26
27
26
29
30
29
32
33
32
35
36
35
38
39
38
41
42
41
44
45
44
47
48
47
50
51
50
53
54
53
56
57
56
59
60
59
62
63
62
65
66
65
68
69
68
71
72
71
74
75
74
77
78
77
80
81
80
83
84
83
86
87
86
89
90
89
92
93
92
95
96
95
98
99
98
101
102
...

output:

767713260

result:

ok single line: '767713260'

Test #12:

score: -100
Wrong Answer
time: 56ms
memory: 9496kb

input:

100000
37545
63739
77335
76669
41730
7658
16542
96644
93229
26821
44918
85782
59893
20668
23347
7485
66696
52156
83919
58211
21501
74582
15535
95723
93846
56664
45820
76652
119
87653
94275
7476
10922
22482
97813
44052
1939
82364
97592
50820
14029
72907
60215
75940
69655
61420
91810
80030
20680
10647...

output:

146248044

result:

wrong answer 1st lines differ - expected: '547375115', found: '146248044'