### PROBLEM LINKS

### DIFFICULTY

MEDIUM

# EXPLANATION

Let **N** = **A**_{1} + **A**_{2} + … + **A _{k}** (

**A**

_{1}?

**A**

_{2}? … ?

**A**> 0) be a partition of the integer

_{k}**N,**and let

**k ? M**. And let

**B**be the number of

_{i}**A**. Then

_{j}= i**f(M, N, X)**has

**M!**/ (

**B**

_{1}! *

**B**

_{2}! * … *

**B**! * (

_{N}**M - k)**!) terms which equals to cos(

**A*** cos(

_{1}X / N)**A*** … * cos(

_{2}X / N)**A**), since the number of patterns can be derived from multinomial theorem. And, of course, any term in

_{K}X / N**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**! / (**B**_{1}! * **B**_{2}! * … * **B _{N}**! * (

**M**-

**k**)!) * cos(

**A**) * cos(

_{1}X / N**A**) * … * cos(

_{2}X / N**A**). Note that the number of partitions (A000041) of

_{K}X / N**N**is not so large, at most

**5604**. And also note that

**M**! / (

**B**

_{1}! *

**B**

_{2}! * … *

**B**! * (

_{N}**M - k**)!) can be calculated with

**O(N)**time, since it is calculated as

**M * (M**- 1) * … * (

**M**-

**B**

_{SUM}+ 1) / (

**B**

_{1}! *

**B**

_{2}! * … *

**B**!), where

_{N}**B**

_{SUM}=

**B**

_{1}+

**B**

_{2}+ … +

**B**. Therefore this algorithm is fast enough.

_{K}Alternatively one can use DP to solve this problem in

**O(N**

^{3}) 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.