QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#191444 | #5487. Movie Night | yaroslav06 | WA | 56ms | 9496kb | C++14 | 1.4kb | 2023-09-29 23:09:00 | 2023-09-29 23:09:00 |
Judging History
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'