The only way so solve it that I've found is to use https://en.wikipedia.org/wiki/Rencontres_numbers and calcuate , but I don't like that. Is there other way? Can we use inclusion-exclusion formula to calculate it?

# | User | Rating |
---|---|---|

1 | ecnerwala | 3648 |

2 | Benq | 3580 |

3 | orzdevinwang | 3570 |

4 | cnnfls_csy | 3569 |

5 | Geothermal | 3568 |

6 | tourist | 3565 |

7 | maroonrk | 3530 |

8 | Radewoosh | 3520 |

9 | Um_nik | 3481 |

10 | jiangly | 3467 |

# | User | Contrib. |
---|---|---|

1 | maomao90 | 174 |

2 | adamant | 164 |

3 | awoo | 163 |

4 | TheScrasse | 160 |

5 | nor | 159 |

6 | maroonrk | 156 |

7 | SecondThread | 150 |

8 | -is-this-fft- | 147 |

9 | pajenegod | 146 |

10 | BledDest | 144 |

The only way so solve it that I've found is to use https://en.wikipedia.org/wiki/Rencontres_numbers and calcuate , but I don't like that. Is there other way? Can we use inclusion-exclusion formula to calculate it?

↑

↓

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/13/2024 06:56:19 (i2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Why don't you like that?

because I don't understand that

What exactly don't you understand?

Obvious formula, he just troll

Yes we can. Notice that

D(N,k) =C(N,k)·!(N-k), and derangement of (N-k) can be calculated this wayPlease elaborate

What does "fixed points" mean?

a_{i}=iThere is another solution involving dynamic programming and constructing permutations.

First, consider the following way of constructing all permutations of length

nfrom all permutations of length (n- 1). Suppose we have a permutation of length (n- 1), for example,n= 6 and the permutation is`a b c d e`

. Put the new elementnat the back of the permutation. Then, swap the new last element with one of the elements, including itself. We getndifferent permutations:Note that different permutations

`a b c d e`

produce different permutations of length 6. So, this process allows to construct all permutations of lengthnfrom all permutations of length (n- 1).Now, look what happens with the fixed points during this process. Let there be

kfixed points in the permutation`a b c d e`

. Clearly, 0 ≤k≤ (n- 1).If we swap

nwithn, the number of fixed points increases by 1 (all the fixed points from`a b c d e`

plus the new elementn).If we swap

nwith a fixed point (kpossibilities), the number of fixed points decreases by 1.If we swap

nwith an element which is already not in its place ((n- 1) -kpossibilities), the number of fixed points stays constant.We can now formulate a “forward” dynamic programming approach. If we know

D(n- 1,k) =x, it contributes:xtoD(n,k+ 1),x·ktoD(n,k- 1) andx·((n- 1) -k) toD(n,k).The “backward” dynamic programming solution (of the form

D(n,k) = ...) can also be formulated.The problem of counting permutations with

kfixed point is addressed in the book generatingfunctionology, as an example of the interpretation of the inclusion-exclusion principle in terms of generating functions.The approach yields the result that for a given

n, ifa_{k}is the number of permutations of sizenwith exactlykfixed points, then its ordinary power series generating function is .This gives the formula

, so we can compute the result in .