It seems that some people haven't got the idea of this problem 285E - Позиции в перестановке while the tutorial is still incomplete so I'd like to write some explanations about it.

A common approach for this kind of problem is DP. What we do here is to choose numbers for the good positions first, then fill the others later on. Let `f(i, j, k)`

is the number of ways to choose j good positions in the first i-th position and k is a 2-bit number that represents whether number i and number i + 1 is already used or not. The DP transition is quite simple.

Let `F(j)`

is the number of permutations with j good positions, then `F(j) = Σ(f(n, j, k)) * (n - j)!`

(because there are n — j numbers left unchosen). However, there are cases we may form some extra good positions when putting these n — j numbers into our permutations, thus `F(j)`

now stores the number of permutations with **at least** j good positions. But we want `F(j)`

to be the number of permutations with **exact** j good positions, so we must exclude those permutations with more than j good positions.

Let's do it in descending order. First `F(n)`

must be the number of permutations with exact n good positions. Hence, we may calculate `F(n - 1)`

based on `F(n)`

, then `F(n - 2)`

based on `F(n - 1)`

and `F(n)`

, and so on... The last part is to calculate how many times `F(j)`

is repeatedly counted in `F(i)`

(i < j), it's simply `C(j, i)`

(the number of ways to choose i good positions from j good positions).

The overall complexity is O(n^2).

Please refer to my submission 3376355 for an implementation.

could you kindly give more details about f(i, j, k) recursive formula?

Why not just calculate

`F(j) — F(j+1)`

, wouldn't it be the number of permutations with exact j good positions?No. Because F(j + 1) might be counted more than once in F(i). For example when n = 2, k = 1: F(2) = 1, F(1) = 2. Clearly, the answer is 0 because F(2) is counted twice in F(1).

Oh.. how could I not think of that. Thanks.

I think your explanation about the the state f(i, j, k) should be clearer, the 2-bit k that represents whether i and number i + 1 are used or not, is in fact if number i is present in "good" position i-1 and if i+1 is present in "good" position i, respectively.

Yes, that's what I mean. I think everyone can understand it easily so I try to make it short. Anyway, thanks for your interpretation.

I have different solution which directly call F[i][j] is the number of permutations of length i with j good positions. We will add one more dimension to handle some states, so it will be F[i][j][k]. We can create new permutation with length i+1 from a permutation(i,j) by insert (i+1) to the end of the permutation . After that, we swap (i+1) with the the element from 1 to i. By this way, we can retain at least j-1 good position in the permutation to form new permutation.

To manage DP accurately, we have to keep some extra property along with F[i][j]. The third dimension in DP formula of my approach handles whether the ith element = (i-1) and whether the (i-1)th = i. The state can be maped to 0->3. In my solution , there is one more state F[i][j][4] means number of permutation of length i with j good positions

having i at the end(a[i]=i)because this state can not be demonstrated as I mentioned before.About the transition of F[i][j]. Let me call the element having value i is uth. There are 4 ways of swap, 1st: swap with "no good" positions nor uth nor ith, 2nd: swap with good positions nor uth nor ith, 3rd: swap with uth, 4th: swap with ith

This is my submission. It might be confusing because of my bad implement. http://mirror.codeforces.com/contest/285/submission/3404593

That's what i can really understand,thank you very much!!

What is a simple transfer equation like？I can't understand.