Codechef PARSIN

题目大意

求以下的式子：

其中N很大,M<=30

Solution

首先列出dp方程
设$F(n,m)=\sum _{i=1}^nF(n-i,m-1)\times sin(i\times x)$
这是暴力，然后我们尝试将$sin(i\times x)$变成其他东西

预备知识

二倍角公式：
$cos(2\alpha)=cos^2(\alpha)-sin^2(\alpha)=2cos^2(\alpha)-1$
$sin(2\alpha)=2cos(\alpha)sin(\alpha)$
和差化积：
$cos(\alpha+\beta)=cos(\alpha)cos(\beta)-sin(\alpha)sin(\beta)$
$sin(\alpha+\beta)=sin(\alpha)cos(\beta)+sin(\beta)cos(\alpha)$
根据三角函数定义：
$sin^2(\alpha)+cos^2(\alpha)=1$

推导

$sin(i\times x)= \begin{cases} sin((k-1)x+x)=cos(x)sin((k-1)x)+sin(x)cos((k-1)x)\\ sin((k-2)x+2x)=cos(2x)sin((k-2)x)+sin(2x)cos((k-2)x) \end{cases}$
$2sin(k\times x)\\=sin((k-1)x+x)+sin((k-2)x+2x)\\=cos(x)sin((k-1)x)+sin(x)cos((k-1)x)+cos(2x)sin((k-2)x)+sin(2x)cos((k-2)x)\\=cos(x)sin((k-1)x)+sin(x)cos((k-1)x)+2cos^2(x)sin((k-2)x)-sin((k-2)x)+2cos(x)sin(x)cos((k-2)x)\\=cos(x)[sin((k-2)x)cos(x)+sin(x)cos((k-2)x)]+sin(x)cos((k-1)x)+2cos^2(x)sin((k-2)x)-sin((k-2)x)+2cos(x)sin(x)cos((k-2)x)\\=3cos^2(x)sin((k-2)x)+3cos(x)sin(x)cos((k-2)x)+sin(x)[cos((k-2)x)cos(x)-sin((k-2)x)sin(x)]-sin((k-2)x)\\=3cos^2(x)sin((k-2)x)+4cos(x)sin(x)cos((k-2)x)-sin((k-2)x)-sin^2(x)sin((k-2)x)\\=4cos^2(x)sin((k-2)x)+4cos(x)sin(x)cos((k-2)x)-2sin((k-2)x)\\=4cos(x)[cos(x)sin((k-2)x)+sin(x)cos((k-2)x)]-2sin((k-2)x)\\=4cos(x)sin((k-1)x)-2sin((k-2)x)\\即：\\2sin(k\times x)=4cos(x)sin((k-1)x)-2sin((k-2)x)\\sin(k\times x)=2cos(x)sin((k-1)x)-sin((k-2)x)\\\therefore\\F(n,m)=\sum _{i=1}^nF(n-i,m-1)\times sin(i\times x)\\=\sum _{i=2}^nF(n-i,m-1)\times sin(i\times x)+F(n-1,m-1)\times sin(x)\\=\sum _{i=2}^nF(n-i,m-1)\times2cos(x)\times sin((i-1)x)-\sum_{i=2}F(n-i,m-1)\times sin((i-2)x)+F(n-1,m-1)\times sin(x)\\=2cos(x)\times\sum _{i=2}^nF(n-i,m-1)\times sin((i-1)x)-\sum_{i=2}F(n-i,m-1)\times sin((i-2)x)+F(n-1,m-1)\times sin(x)\\=F(n-1,m)\times2cos(x)-F(n-2,m)+F(n-1,m-1)\times sin(x)$

矩阵乘法

于是我们发现F(n,m)只与F(n-1,m),F(n-2,m),F(n-1,m-1)有关，于是我们可以用一个2m*2m的矩阵来做快速幂，最终就可以得出结果了。

。。。推到脑抽