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

Автор elizabeth_zou_fanboi, история, 5 часов назад, По-английски

a permutation is valid only if |ai — i| != k for all 1<=i<=n. Count the number of valid permutations.

Constraints: 2 ≤ N ≤ 2000

1 ≤ K ≤ N − 1

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

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

Auto comment: topic has been updated by elizabeth_zou_fanboi (previous revision, new revision, compare).

»
4 часа назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

"how many satisfy |a_i − i| ≠ K"

Could you clarify please?

»
3 часа назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

Step 1: Generate all permutations of length $$$N$$$.

Step 2: Perform a linear scan, adding $$$1$$$ to the result if $$$|a_i - i| \ne k$$$ for all $$$i$$$ from $$$1$$$ to $$$N$$$.

Space complexity is $$$O(N \cdot N!)$$$ and time complexity is $$$O(N \cdot N!)$$$.

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

I have a solution with inclusion-exclusion.

For some permutation $$$p$$$, let $$$x$$$ be the number of indices $$$i$$$ with $$$|p_i - i| = k$$$.

Let $$$f(i)$$$ be the sum over all permutations of $$$x \choose i$$$. The answer is $$$\sum_{i=0}^{n} (-1)^i f(i)$$$.

To compute $$$f(i)$$$, you can count the number of ways to choose a subset of indices of size $$$i$$$, and assign $$$p_i$$$ values to it such that all indices $$$i$$$ in the subset satisfy $$$|p_i - i| = k$$$, and multiply that by $$$(n - i)!$$$. You can compute a dp for each residue class modulo $$$k$$$, and then merge the answers of each residue class.

Is there a more simple solution?