I had a O(n² / 2) DP but that only gets 42? Is expected solution better than that? :/

Mine is to have state DP(pairs, non-pairs) where pairs is number of elements that exist is pairs, and non-pairs is number of element that dont. We have 2 option: Either put an element that exist in pair or one that doesnt. For option 1, we add DP(pair-1, non-pair+1) and subtract DP(pair-1, non-pair) and for option 2 we simply add DP(pair, non-pair-1).

dp[a][b][c] = ((1 — c) * (a * dp[a — 1][b][0] + b * dp[a + 1][b — 1][1]) + c * ((a — 1) * dp[a — 1][b][0] + b * dp[a+1][b-1][1])) % mod

the answer will be dp[number_of_numbers_which_appear_once][number_of_numbers_which_appear_twice][0]

I don't know how it is solved so good, for me it was pretty hard. I got idea and couldn't code on the time. Here is my idea:

First remove single elements, we will add them at the end it is easy...

Now we will calculate DP[ i ][ j ] number of permuations with first i pairs such that we have exactly j neighbours. Answer is DP[ number of pairs] [ 0 ]. How we can caluclate this DP, we can see all possible situations of previous condition and adding that two elements ( in that station we can come from stations DP [i-1] [ j -1] , DP [i-1] [ j ], DP [i-1] [ j + 1], DP [i-1] [ j +2] )...

I didn't read editorial, but I believe this is correct.

Let's count the permutations which don't satisfy the statement and then subtract this number from the number of all permutations. dp[i][j] — number of permutations of i elements, j of which occur twice, such that there is at least one pair of adjacent equal numbers. dp[i][0] is 0 for any i. To calculate dp[i][j], there are the following possibilities:

1. Use some element which occurs once. This can be done only if 2 * j < i. The state we go to is dp[i - 1][j].

2. Use some element which occurs twice, but use only one of its occurrences. We go to state dp[i - 1][j - 1] and multiply it by j, because we have j possible elements to choose from. Note that we should now subtract dp[i - 2][j - 1] * j because we don't want to put both of the equal elements here.

3. Put some pair of equal elements here, which immediately makes all possible permutations bad. We have j possible pairs to choose from. Once we choose such pair, we remain with i - 2 elements, from which there are j - 1 pairs of equal elements. And all such permutations are bad. So we simply add .

I didn't use DP but combinatorics instead.

Firstly, the number of permutations of a multiset having N elements, including M duplications, is N!/(2^M). Let's denote M as the total number of duplications in the initial multiset.

Let's calculate the number of permutations having at least K successive equal pairs:

- There are R=(N-K*2) remaining elements which do not belongs to these pairs.
- There are (M_choose_K * K!) ways to select and order the pairs.
- There are R!/(2^(M-K)) ways to order the remaining elements.
- There are (K+R)_choose_K ways to "merge" the selected pairs with the remaining elements.

The formula is (M_choose_K * K!) * R!/(2^(M-K)) * (K+R)_choose_K.

Then I used the inclusion-exclusion principle to obtain the answer.

My code: http://pastebin.com/B2ZsF4Zc

Can be solved in O(n) using inclusion-exclusion principle. Lets say there are c distinct elements with count 2, then answer is sum(ncr(c,i)*(n-i)!/pow(2,c-i)) for all i= 0 to c. Code

I just solved it using dp(i)(j)(b) -> Processing i pairs, j individual elements, with b true if the last element was the first of a pair.

dp(i,j,b):
 if b == false:
  return i * bt(i - 1, j + 1, true) + j * bt(i, j - 1, false)
 else if b == true:
  return  i * bt(i - 1, j + 1, true) + (j-1) * bt(i, j - 1, false)

Then the answer would be dp(number_of_pairs, number_of_numbers_which_appear_once, false).

I coded this dp inside the contest but I had j=0 and I was thinking of a way to add the individual elements after this dp :( I WAS SO CLOSE
My AC code: pastebin

I use stupid solution (n**2)q and it got accepted.

We unlocked the codes, now you can see them in submissions tab.

What is your criteria in determining whether the problem is pointless or not?

tin[i] means time at which we first arrive at node i during our dfs traversal.