Test#1
3 3
1 2 3
ans:27

Test#2
2 6
1 3
ans:36

Test#3
3 6
3 4 5
ans: 180

Test#4
1 5
3
ans:5

Test#5
1 2
1
ans:1

Test#6
3 2
1 2 2
ans:4

Maybe new problem with increase S,K)

5 500
250 250 250 250 250
-------------------
22288580

I use set when solve this task :D
And i have AC with 2.453s
But hashes work faster 0.625s (sorry for my bad english)

Edited by author 10.09.2013 21:09

What I must write if n=1?
Please, give me answers for tests:
1 1
1
(yes, it's uncorrect ;)

1 2
1

1 3
1

1 4
4

Edited by author 08.04.2007 16:10

http://www.cplusplus.com/reference/algorithm/prev_permutation.html
"If the function can determine the previous smaller permutation, it rearranges the elements as such and returns true. If that was not possible (because it is already at the smallest), it rearranges the elements according to the last permutation (sorted in descending order) and returns false."

On Timus std::prev_permutation function doesn't return false ever.

This code gets TLE:

    std::vector<int> v(5);
    for (int i = 0; i < 2; ++i)
        v[i] = 1;
    while (std::prev_permutation(v.begin(), v.end()));

Structure vector<int>Pos[100][100] gave Ac.
With O(lgN) find(S) and O(N) insert(S)
where S- new position
set<int>Pos[100][100] led to MLE
Thus only all position generating without
any combinatorical counting.
Who can advice more effective structure
for store position, please, do it.

Does anybody solve it without hash?
I can get just 1 right hash from several hundreds