CF2008D Sakurako's Hobby

For a certain permutation $ p $ $ ^{\text{∗}} $ Sakurako calls an integer $ j $ reachable from an integer $ i $ if it is possible to make $ i $ equal to $ j $ by assigning $ i=p_i $ a certain number of times. If $ p=[3,5,6,1,2,4] $ , then, for example, $ 4 $ is reachable from $ 1 $ , because: $ i=1 $ $ \rightarrow $ $ i=p_1=3 $ $ \rightarrow $ $ i=p_3=6 $ $ \rightarrow $ $ i=p_6=4 $ . Now $ i=4 $ , so $ 4 $ is reachable from $ 1 $ . Each number in the permutation is colored either black or white. Sakurako defines the function $ F(i) $ as the number of black integers that are reachable from $ i $ . Sakurako is interested in $ F(i) $ for each $ 1\le i\le n $ , but calculating all values becomes very difficult, so she asks you, as her good friend, to compute this. $ ^{\text{∗}} $ A permutation of length $ n $ is an array consisting of $ n $ distinct integers from $ 1 $ to $ n $ in arbitrary order. For example, $ [2,3,1,5,4] $ is a permutation, but $ [1,2,2] $ is not a permutation (the number $ 2 $ appears twice in the array), and $ [1,3,4] $ is also not a permutation ( $ n=3 $ , but the array contains $ 4 $ ).

N/A

N/A