PROBLEM LINKS
DIFFICULTY
MEDIUM
EXPLANATION
Let N = A1 + A2 + … + Ak (A1 ? A2 ? … ? Ak > 0) be a partition of the integer N, and let k ? M. And let Bi be the number of Aj = i. Then f(M, N, X) has M! / (B1! * B2! * … * BN! * (M - k)!) terms which equals to cos(A1 X / N) * cos(A2 X / N) * … * cos(AK X / N), since the number of patterns can be derived from multinomial theorem. And, of course, any term in f(M, N, X) corresponds to exactly one partition of N.
The model solution is generating all partitions of N, then calculating the sum of N! / (B1! * B2! * … * BN! * (M - k)!) * cos(A1 X / N) * cos(A2 X / N) * … * cos(AK X / N). Note that the number of partitions (A000041) of N is not so large, at most 5604. And also note that M! / (B1! * B2! * … * BN! * (M - k)!) can be calculated with O(N) time, since it is calculated as M * (M - 1) * … * (M - BSUM + 1) / (B1! * B2! * … * BN!), where BSUM = B1 + B2 + … + BK. Therefore this algorithm is fast enough.
Alternatively one can use DP to solve this problem in O(N3) time. See as a reference the first AC solution for this problem by Michael Kolupaev.
SETTER’S SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here.