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; } }