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

Автор YouKn0wWho, 3 года назад, По-английски

I was experimenting on the following problem for quite a long time:

You are given two integers $$$n$$$ and $$$k(1 \le k\le n \le 10^5)$$$. You have to find the number of permutations with length $$$n$$$ that can be obtained as a suffix array of at least one integer sequence $$$a_1, a_2, \ldots, a_n$$$ s.t. $$$1\le a_i \le k$$$. Output it modulo $$$998, 244, 353$$$.

Definition of Suffix Array for an integer sequence

I didn't have any clue when I came up with the problem. It's really hard to find any specific properties of a permutation which will ensure that there exists a sequence which will generate the permutation as its suffix array.

So then I wrote a brute force over smaller numbers. And it turned out that there exists an OEIS sequence for this problem! And the solution to our problem is $$$F(n, k) = \sum_{i = 0}^{k}{(-1)^i(k-i)^n {n \choose i}}$$$

But there is a breathtaking twist! Before I describe it, let's look at the Eulerian numbers. What are they? The Eulerian number $$$A(n, k)$$$ is the number of permutations of the numbers from $$$1$$$ to $$$n$$$ in which exactly $$$k$$$ elements are greater than the previous element (permutations with $$$k$$$ "ascents").

It turns out that $$$F(n, k) = \sum_{i = 0}^{k - 1}{A(n, i)}$$$. That means the solution to our problem is exactly equal to the number of permutations with $$$<k$$$ ascents!

The twist here is that when I printed out the permutations in my problem, they are not the permutations with $$$<k$$$ ascents! That means there is a bijection between the permutations with $$$<k$$$ ascents and the permutations that can be obtained as a suffix array of at least one integer sequence $$$a_1, a_2, \ldots, a_n$$$ s.t. $$$1\le a_i \le k$$$.

So my two questions are:

  • How does the bijection exist?
  • Is there any specific property of a permutation which will ensure that there exists a sequence $$$a_1, a_2, \ldots, a_n$$$ s.t. $$$1\le a_i \le k$$$ which will generate the permutation as its suffix array?
  • Проголосовать: нравится
  • +132
  • Проголосовать: не нравится

»
3 года назад, # |
Rev. 2   Проголосовать: нравится +63 Проголосовать: не нравится

I read this long time ago, due to the same problem idea. If I remember correctly, you need to look for descents on $$$p^{-1}(p+1)$$$, where the addition is taken modulo $$$n$$$. Note that the above is a bijection on $$$S_n$$$.

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

I couldn't resist checking the blog post after seeing such a catchy title.

»
3 года назад, # |
Rev. 2   Проголосовать: нравится +17 Проголосовать: не нравится

I remember a problem named "Suffix Array" from CTSC 2016. The problem is: given $$$n$$$, $$$m$$$ and $$$c_1,c_2 \cdots c_m$$$, count the number of different suffix arrays which can be generated by strings satisfying that the $$$i$$$-th character appears no more than $$$c_i$$$ times. $$$n, c_i \leq 500$$$

It is a very hard problem and I have no idea how to solve it, but the solution claims that the suffix array of string $$$s$$$ is $$$p$$$ iff the condition below is satisfied:

Let $$$p_{0} = n+1$$$,

if $$$p_i + 1$$$ appears after $$$p_{i+1} + 1$$$ then $$$s_{p_i} < s_{p_{i+1}}$$$

if $$$p_i + 1$$$ appears before $$$p_{i+1}+1$$$ then $$$s_{p_i} \leq s_{p_{i+1}}$$$

With this claim it is easy to get your conclusion

Sorry for my poor English, written in a hurry as I have to leave now.