| # | User | Rating |
|---|---|---|
| 1 | tourist | 3985 |
| 2 | jiangly | 3814 |
| 3 | jqdai0815 | 3682 |
| 4 | Benq | 3529 |
| 5 | orzdevinwang | 3526 |
| 6 | ksun48 | 3517 |
| 7 | Radewoosh | 3410 |
| 8 | hos.lyric | 3399 |
| 9 | ecnerwala | 3392 |
| 9 | Um_nik | 3392 |
| # | User | Contrib. |
|---|---|---|
| 1 | cry | 169 |
| 2 | maomao90 | 162 |
| 2 | Um_nik | 162 |
| 4 | atcoder_official | 161 |
| 5 | djm03178 | 158 |
| 6 | -is-this-fft- | 157 |
| 7 | adamant | 155 |
| 8 | awoo | 154 |
| 8 | Dominater069 | 154 |
| 10 | luogu_official | 150 |
Given an integer n you need to calculate the number of distinct permutations {1, 2, 3, ..., n} such that the permutation represents a linear max heap.
In other words for each position from 1 to n: p[i] > p[2*i] and p[i] > p[2*i+1]
Example: Input: 4 Output: 3
I need help solving this problem, at least a hint please.
Here
Is the runtime O(N) (assume we have preprocessed factorial and modular inverse of factorial) .
No, it's O(NlogN), because the modular inverse is calculated in O(log), atleast I don't know how to do it faster :)
If you know
, you can find out 
in O(1). 
can be computed in O(n).
Ohh yeah I just noticed it now
(n!) - 1 = (n + 1) * ((n + 1)!) - 1
Is this correct ?
Yes, that's the recurrence. Another way to do it, using one more array, is to precompute
for every i in 
, then 
. Here are some ideas to compute inverse efficiently.
I don't think it would be possible to precompute for all i because M can be very large (109 + 7)
In that problem M is 666013.
Yeah you are right . The preprocessing part takes O(NlogN) , and the part to calculate the number of heaps till N can be done in O(N) using the recurrence that you've posted . So overall it's O(NlogN) .
Thanks!