CSES - Leirikisa 4

Submission details
Task:	paleta
Sender:	zxc
Submission time:	2016-08-01 16:20:31 +0300
Language:	C++
Status:	READY
Result:	100

Feedback
group	verdict	score
#1	ACCEPTED	100

Test results
test	verdict	time
#1	ACCEPTED	0.06 s	details
#2	ACCEPTED	0.06 s	details
#3	ACCEPTED	0.06 s	details
#4	ACCEPTED	0.06 s	details
#5	ACCEPTED	0.06 s	details
#6	ACCEPTED	0.06 s	details
#7	ACCEPTED	0.07 s	details
#8	ACCEPTED	0.06 s	details
#9	ACCEPTED	0.06 s	details
#10	ACCEPTED	0.05 s	details
#11	ACCEPTED	0.06 s	details
#12	ACCEPTED	0.05 s	details
#13	ACCEPTED	0.07 s	details
#14	ACCEPTED	0.06 s	details
#15	ACCEPTED	0.06 s	details
#16	ACCEPTED	0.06 s	details
#17	ACCEPTED	0.07 s	details
#18	ACCEPTED	0.08 s	details
#19	ACCEPTED	0.07 s	details
#20	ACCEPTED	0.44 s	details
#21	ACCEPTED	0.06 s	details
#22	ACCEPTED	0.44 s	details
#23	ACCEPTED	0.06 s	details

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1e9+7;
const int MN = 1e6+100;
ll ex(ll a, ll e) {
    ll res = 1;
    for(; e; e/=2) {
	if(e&1) {
	    res *= a;
	    res %= MOD;
	}
	a *= a;
	a %= MOD;
    }
    return res;
}
ll dp[MN];
vector<int> v[MN];
int par[MN];
bool used[MN];
int f(int x, vector<int> & v2) {
    used[x] = 1;
    if(used[par[x]]) {
	if(par[x] == x) {
	    v2.push_back(x);
	    return 0;
	}
	v2.push_back(par[x]);
	v2.push_back(x);
	return 1;
    }
    int q = f(par[x], v2);
    if(q == 0) {
	used[x] = 0;
	return 0;
    }
    if(x == v2[0]) {
	return 0;
    }
    v2.push_back(x);
    return 1;
}
int f2(int x) {
    used[x] = 1;
    ll ret = 1;
    for(auto y: v[x]) {
	if(!used[y]) {
	    ret += f2(y);
	}
    }
    return ret;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll n,k;
    cin>>n>>k;
    dp[1] = k;
    dp[2] = k*(k-1)%MOD;
    dp[3] = k * (k-1)%MOD*(k-2)%MOD;
    for(int i = 4; i < MN; ++i) {
	dp[i] = (dp[i-2]*(k-1) + dp[i-1]*(k-2))%MOD;
    }
    ll ans = 1;
    int lol = 0;
    for(int i = 1; i <= n; ++i) {
	int x;
	cin>>x;
	par[i] = x;
	v[x].push_back(i);
	if(x == i) ++lol;
    }
    if(lol != n && k == 1) {
	cout<<0<<'\n';
	return 0;
    }
    for(int i = 1; i <= n; ++i) {
	if(!used[i]) {
	    vector<int> sykli;
	    f(i, sykli);
	    ans *= dp[sykli.size()];
	    ans %= MOD;
	    if(sykli.size() > 1 && sykli.size() % 2 == 1 && k == 2) {
		cout<<0<<'\n';
		return 0;
	    }
	    //cout<<sykli.size()<<'\n';
	    //cout<<dp[sykli.size()]<<'\n';
	    for(auto y: sykli) {
		ll q = f2(y)-1;
		ans *= ex(k-1, q);
		ans %= MOD;
	    }
	}
    }
    cout<<ans<<'\n';

}

Test details

Test 1

Verdict: ACCEPTED

input
`2 3 2 1` view save

correct output
`6` view save

user output
`6` view save

Test 2

Verdict: ACCEPTED

input
`3 4 2 3 1` view save

correct output
`24` view save

user output
`24` view save

Test 3

Verdict: ACCEPTED

input
`3 4 2 1 1` view save

correct output
`36` view save

user output
`36` view save

Test 4

Verdict: ACCEPTED

input
`10 4 3 10 7 9 1 4 8 5 6 2` view save

correct output
`69120` view save

user output
`69120` view save

Test 5

Verdict: ACCEPTED

input
`10 2 9 4 2 5 8 10 6 3 1 7` view save

correct output
`0` view save

user output
`0` view save

Test 6

Verdict: ACCEPTED

input
`20 6 15 16 6 12 8 2 11 4 14 17 8 11...` view save

correct output
`749062329` view save

user output
`749062329` view save

Test 7

Verdict: ACCEPTED

input
`10 3 10 7 6 5 9 2 3 6 4 1` view save

correct output
`1296` view save

user output
`1296` view save

Test 8

Verdict: ACCEPTED

input
`100 6 70 62 57 34 87 73 81 45 11 25 ...` view save

correct output
`170647921` view save

user output
`170647921` view save

Test 9

Verdict: ACCEPTED

input
`5 7 2 3 4 5 5` view save

correct output
`9072` view save

user output
`9072` view save

Test 10

Verdict: ACCEPTED

input
`200 13 88 97 79 1 184 104 127 159 157...` view save

correct output
`798243726` view save

user output
`798243726` view save

Test 11

Verdict: ACCEPTED

input
`5 2 1 2 3 4 5` view save

correct output
`32` view save

user output
`32` view save

Test 12

Verdict: ACCEPTED

input
`1000 17 321 466 231 684 53 480 95 61 5...` view save

correct output
`799039396` view save

user output
`799039396` view save

Test 13

Verdict: ACCEPTED

input
`5 1 1 2 3 4 5` view save

correct output
`1` view save

user output
`1` view save

Test 14

Verdict: ACCEPTED

input
`2000 27 545 945 734 555 1974 1119 694 ...` view save

correct output
`87259530` view save

user output
`87259530` view save

Test 15

Verdict: ACCEPTED

input
`5 4 2 3 4 5 1` view save

correct output
`240` view save

user output
`240` view save

Test 16

Verdict: ACCEPTED

input
`20000 207 4712 13482 9751 10677 2744 326...` view save

correct output
`920405949` view save

user output
`920405949` view save

Test 17

Verdict: ACCEPTED

input
`10 9 2 3 4 5 6 7 8 9 10 1` view save

correct output
`73741825` view save

user output
`73741825` view save

Test 18

Verdict: ACCEPTED

input
`100000 137 35216 66352 76631 39149 68563 ...` view save

correct output
`873619169` view save

user output
`873619169` view save

Test 19

Verdict: ACCEPTED

input
`5 2 2 1 3 4 5` view save

correct output
`16` view save

user output
`16` view save

Test 20

Verdict: ACCEPTED

input
`1000000 1337 157667 207184 572776 559466 52...` view save

correct output
`815275681` view save

user output
`815275681` view save

Test 21

Verdict: ACCEPTED

input
`5 2 2 3 4 5 1` view save

correct output
`0` view save

user output
`0` view save

Test 22

Verdict: ACCEPTED

input
`1000000 137037 302969 577811 4130 64 558319 7...` view save

correct output
`387136640` view save

user output
`387136640` view save

Test 23

Verdict: ACCEPTED

input
`6 2 2 3 4 5 6 1` view save

correct output
`2` view save

user output
`2` view save

Leirikisa 4

paleta

Code

Test details

Test 1

Test 2

Test 3

Test 4

Test 5

Test 6

Test 7

Test 8

Test 9

Test 10

Test 11

Test 12

Test 13

Test 14

Test 15

Test 16

Test 17

Test 18

Test 19

Test 20

Test 21

Test 22

Test 23

Tasks

Submissions (zxc)