The constraints in the first sub task are very small, so a simple brute force will be enough in order to get a nonzero score at
In general case, let’s consider the following problem: you are given the number of each symbol’s occurences and now
you’re asked to calculate the number of different palindromes that one can obtain by permutting all these letters in some way.
Let’s consider that the i-th alphabet letter occurs A* times, i.e. ‘a’ occurs A times, ‘b’ occurs A times, and so on.
Then, we can make some observations. At first, if A contains more than one odd number (i.e. there are two letters that occurs
odd number of times), then it’s impossible to create a palindrome at all. So, in this case the answer if zero. Otherwise, if there
is one such letter, then this letter will be the “center” of the palindrome, so we place it in the center and decrease the number
of these letters. Now, A contains only even numbers. It’s a well known fact that knowing the length of the palindrome, let’s call
it K, and the first (K+1)/2 letters of it, it’s trivial to reconstruct it. Also, it’s not hard to see that the number of occurrences
of each letter in the left half of a palindrome string equals to the number of occurences of each letter in the right half of a
palindrome string. Based on this, we just have to calculate the number of different ways to place (K+1)/2 letters of 10 types
(i.e. ‘a’ to ‘i’), where the amount of letter of every type if known. It’s a well known combinatorial problem and the answer will
be ((K+1)/2)!/((A/2)! * (A/2)! * … * (A/2)!). It is asked to output the result modulo a prime number, so you can use a well
known modular multiplicative inverse calculation trick in order to calculate the answer. With a proper implementation, overall
complexity of a single such a query will be O(alphabet).
So now, in the second subtask you can perform all the operations in a simple way. When you need to reverse the string, you can
do it in O(N) time. To answer the queries of another type, you can calculate the array A and then solve the problem in O(alphabet)
complexity, which is in fact very fast. So, this way we get O(M * N * alphabet) solution.
In order to pass the last sub task, you need to use some advanced data structure. Writer’s solution uses treap, which seems the
easiest way to solve the problem. The queries treap should maintain are quite standard for this structure - namely reversing the
segment and counting the number of some letter’s occurences, so it shouldn’t cause any problem.
Can be found here
Can be found here