GG_EZ_DOGS's blog

Help pls
By GG_EZ_DOGS, history, 3 years ago, In English

Can anyone help me to solve this, please?

Find the number of different permutations of length n such that the number of indices i (1 <= i <= n-1) where p[i] > p[i+1] is equal to K.

UPD: 1 <= n <= 3000, 0 <= k < n.

  • Vote: I like it
  • +1
  • Vote: I do not like it

»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +4 Vote: I do not like it

Seems to me like you need Connected Component DP: https://mirror.codeforces.com/blog/entry/92602

→ Reply
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

can we solve it when n <= 3e5?

→ Reply