| C. Summing The Lengths of Longest Increasing Subsequences of Permutations |
Compute the sum of the lengths of the longest increasing subsequence of each distinct permutation of (1,2,3,..,n).
In other words, sum over all permutations, w of (1,2,3,..,n), LIS(w). Where LIS(w) is the length of the longest increasing subsequence of w. However, this number increases exponentially. In the problem we are interested only in the first five digits. Also, note that each subsequence does not have to be contiguous. For example, the longest increasing subsequence of (3,2,4,1,5) is (3,4,5) with length 3.
Hint: You may want to compute a few small values and find a beautiful pattern!!!
The input will consist of at most 100000 lines, each one with just the positive integer n (100<n<100000000).
For each input value, output the first five digits of the sum of the lengths of the longest increasing subsequence of each permuation of (1,2,3,...,n).
101 1001 10001
18945 25487 56933