Упростить выражение (быстро вычислить, для программистов)

[Leox]

Программистам дали сегодня задачу быстро вычислить выражение

$$ S(n,m,x)=\sum_{k_1+k_2+\cdots+k_m=n} \sin(k_1 x) \sin(k_2 x)\cdots \sin(k_m x), k_i \geq 0. $$

Скорее всего ето выражение допускает существенное упрощение, но пока не ясно какое. Наверное в Кнута есть решение.

[venco]

Если программистам, то скорее всего, решать надо без упрощения, но с применением динамического программирования. Каковы ограничения на n и m?

[Leox]

Ограничения такие

$$ 1 \leq n \leq 30,\\ 1 \leq m \leq 1000000000 (10^9),\\ 0 \leq X \leq 6.28 < 2\pi $$

[venco]

Что вы можете сказать про сумму если $n < m$?

[Leox]

venco в сообщении #490667 писал(а):

Что вы можете сказать про сумму если $n < m$?

Она равна нулю, поскольку среди $k_i$ обязательно присутствуют нули и тогда соответствующий синус также равен нулю.

[venco]

Ну вот, остался только случай $n=m$. А там совсем просто.
Странно, конечно, ведь самый интересный случай - $n>m$. Вы не перепутали условия?

-- Сб окт 08, 2011 10:28:24 --

Ааа! Вы уже исправили условия. Так интереснее.

-- Сб окт 08, 2011 10:29:22 --

Ну а теперь применяйте ДП. Сложность получится $n^2$.

[Leox]

спасибо