13259번: 강호의 초대

https://www.acmicpc.net/problem/13259


$O(n^2)$

#include<cstdio>
int n, a[50];
double dp[51], f = 1, r;
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", a + i), dp[i + 1] = dp[i] - (f /= -i - 1);
    for (int i = 0; i < n; i++) {
        int ck[50] = { 0, }, c = 0;
        for (int j = i; !ck[j]; j = a[j]) ck[j] = 1, c++;
        r += dp[c];
    }
    printf("%.9lf", r);
    return 0;
}