dp递推 口胡记录

dp/递推 口胡记录

[SHOI2013] 超级跳马

\(tag\)：矩阵乘法，前缀和

暴力\(dp\)很显然，设\(f_{i,j}\)为从\((1,1)\)跳到\((i,j)\)的方案数，那么有$f_{i,j}= \sum \limits _{j-(2k+1)>0}f _{i/i+1/i-1,j-(2k+1)} $

发现这个东西其实是一直由前面奇偶性相同的一段转移过来的，因此考虑前缀和优化

设\(s_{i,j}=\sum \limits _{j-2k>0} f_{i,j-2k}\)，那么由定义有\(s_{i,j}=s_{i,j-2}+f_{i,j}\)，然后我们再考虑\(f\)怎么由\(s\)转移而来，不难发现\(f_{i,j}=s_{i-1,j-1}+s_{i,j-1}+s_{i+1,j-1}\)，联立两式有\(s_{i,j}=s_{i,j-2}+s_{i,j-1}+s_{i-1,j}+s_{i+1,j-1}\)。

然后这个前缀和显然可以矩乘转移。

[JLOI2015] 有意义的字符串

不看题解连矩乘都想不到，/kk

发现\(\frac{b+ \sqrt{d}}{2}\)的形式和一元二次方程求根公式很像，进过构造可以发现它是方程\(x^2-bx+\frac{b^2-d}{4}=0\)的一个解。

移项后两边同时乘\(x^{n-2}\)有\(x^n=bx^{n-1}-\frac{b^2-d}{4}x^{n-2}\)。

发现这个已经形成了矩乘形式的递推关系，但是初始\(\frac{b+ \sqrt{d}}{2}\)是小数，不方便进行取模。

所以考虑构造\(f(x)=(\frac{b+ \sqrt{d}}{2})^x+(\frac{b- \sqrt{d}}{2})^x\),将两个根\(x1,x2\)带入后两式相加发现有\(f(i)=bf(i-1)-\frac{b^2-d}{4}f(i-2)\)，并且有\(f(0),f(1),b,\frac{b^2-d}{4}\)都为整数。

因此可以直接矩乘计算出\(f(n)\)，再考虑减去\((\frac{b- \sqrt{d}}{2})^n\)的贡献，发现这东西 \(\in \left\{-1,1 \right\}\)分类讨论\(n\)的奇偶性判断答案是否减一即可。

注意用__int128或者龟速乘。