Блог пользователя adityagamer

[HELP] Edu round 86 Problem E
Автор adityagamer, история, 11 месяцев назад, По-английски

Whats wrong with my solution for problem E : https://mirror.codeforces.com/contest/1342/problem/E?

Let c = n-k. Number of ways such that c columns are filled = (Number of ways such that <= c columns are filled) — (Number of ways such that <= c-1 columns are filled)

So formula is $$$ \binom{n}{c}c^n - \binom{n}{c-1}(c-1)^n $$$

  • Проголосовать: нравится
  • -1
  • Проголосовать: не нравится

»
11 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

This comment is to bring this blog in recent and actions.

→ Ответить
»
11 месяцев назад, # |
← Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится

I guess that you got the formula for the number of ways such that $$$\le c$$$ columns are filled is $$${n \choose c} \cdot c^n$$$ as follows: you're trying to choose the columns you can use (this is $$$n \choose c$$$), and then you slot each rook into one of the chosen columns (this is the $$$c^n$$$ part).

Unfortunately, it counts some of the rook placements multiple times. For example, suppose $$$n = 3$$$, $$$c = 2$$$. Then you count the placement "put all rooks in the first column" twice: once for choosing the columns $$$1$$$ and $$$2$$$, once for choosing the columns $$$1$$$ and $$$3$$$.

→ Ответить