There are n people falling in love. Everybody has a unique people he/she loves, and somebody love themselves. But they have a secret agreement: no two people love the same one. To satisfy such a relat
There are n people falling in love. Everybody has a unique people he/she loves, and somebody love themselves. But they have a secret agreement: no two people love the same one. To satisfy such a relationship between n people, we call it a love relationshiptextbf{love relationship}love relationship, denoted by Rmathcal{R}R. Obviously, there are n! different love relationshipstextbf{love relationships}love relationships for n people. And a love relationshiptextbf{love relationship}love relationship can be presented as a permutation. For example, if n = 3, R=[3,1,2]mathcal{R} = [3,1,2]R=[3,1,2] means the first people loves the third people, the second people loves the first people, the third people loves the second people. if A loves B, and B loves C, and C loves A, then we call the relationship between these 3 people 3-love polygontextbf{3-love polygon}3-love polygon. and so on, we can easily define k-love polygontextbf{k-love polygon}k-love polygon for each integer k. Extraordinary, if A loves B and B loves A, we call them 2-love polygontextbf{2-love polygon}2-love polygon. If A loves himself, we call it 1-love polygontextbf{1-love polygon}1-love polygon. Apollo said proudly to Avery: If I konw "how many k-love polygontextbf{k-love polygon}k-love polygon are there in this relationship" for each k, Then I can easily tell you how many relationship combinations might be legal for these n people. But Avery said: No, It's not enough. Let's use f(a1,a2,a3,...,an)f(a_1, a_2, a_3, ..., a_n)f(a1,a2,a3,...,an) to denote the number of love relationshipstextbf{love relationships}love relationships of n people, which can form a1a_1a1 1-love polygontextbf{1-love polygon}1-love polygon, a2a_2a2 2-love polygontextbf{2-love polygon}2-love polygon, ...,and ana_nan n-love polygontextbf{n-love polygon}n-love polygon. If one relationship Rmathcal{R}R of n people can form a1a_1a1 1-love polygontextbf{1-love polygon}1-love polygon, a2a_2a2 2-love polygontextbf{2-love polygon}2-love polygon, ..., ana_nan n-love polygontextbf{n-love polygon}n-love polygon, and f(a1,a2,a3,...,an)f(a_1, a_2, a_3, ..., a_n)f(a1,a2,a3,...,an) is divisible by my favourite number P, then I will feel the relationship Rmathcal{R}R is disgusting. I will tell you my favourite number P, and could you calculate how many relationships are nottextbf{not}not disgusting between these n people? I know this might be too difficult to you, so you can just tell me how many different typestextbf{different types}different types of love relationshipstextbf{love relationships}love relationships are nottextbf{not}not disgusting. Different typetextbf{Different type}Different type: for relationships Ramathcal{R}_aRa and Rbmathcal{R}_bRb , if Ramathcal{R}_aRa will let there be aka_kak k-love polygons for each k∈N+k in mathbb{N}_+k∈N+, Rbmathcal{R}_bRb will let there be bkb_kbk k-love polygons for each k∈N+k in mathbb{N}_+k∈N+, and there exist at least one i, such that ai≠bia_i neq b_iai=bi , then we call love relationships Ramathcal{R}_aRa and Rbmathcal{R}_bRb are different typestextbf{different types}different types. Apollo could not handle this task very well. Could you help him?
