TopCoder SRM592: LittleElephantAndPermutationDiv2

N! のペアを全部試す必要はない。片方の並び順だけを固定したうえでもう片方の順列を全て試して、最後に N! を掛ければ良い。

LINQ の Sum を使ったら TLE だった。こういう next_permutation するだけの問題は大抵 8! の上限だったのだけど、今回は何故か制約が厳しめ。

public class LittleElephantAndPermutationDiv2 {
    static public void Swap<T>(ref T a, ref T b) { T t = a; a = b; b = t; }

    static public bool NextPermutation<T>(T[] array) where T : IComparable<T> {
        int n = array.Length;
        for (int i = n - 2; i >= 0; i--) {
            if (array[i].CompareTo(array[i + 1]) < 0) {
                var index = Array.FindLastIndex(array, v => array[i].CompareTo(v) < 0);
                Swap(ref array[i], ref array[index]);
                Array.Reverse(array, i + 1, n - (i + 1));
                return true;
            }
        }
        Array.Reverse(array);
        return false;
    }

    public long getNumber(int N, int K) {
        var perm = Enumerable.Range(0, N).ToArray();
        long ans = 0;
        do {
            int sum = 0;
            for (int i = 0; i < N; i++) {
                sum += Math.Max(i, perm[i]) + 1;
            }
            if (sum >= K) ans++;
        } while (NextPermutation(perm));
        ans = ans * Enumerable.Range(1, N).Aggregate((a, b) => a * b);
        return ans;
    }
}