PenguinEmperor

作者：丁力煌
关键词：动态规划 快速幂

题目描述

有一个长度为n的环，一个人初始站在0处，第i步可以顺时针走i步或逆时针走i步，求m步之内走回0处的方案数。

$n\leq350, m\leq 10^{18}$

算法1

考虑dp，$f_{i,j}$表示走了i步，停留在j处的方案数。则$f_{i,j}=f_{i-1,j-i}+f_{i-1,j+i}$，后一个下标mod n理解，时间复杂度$O(nm)$

算法2

注意到上面的dp方程对于$mod n$同余的i是相同的所以可以先预处理出从i=0时到i=n时的转移方程，则m时的转移可以视作若干个0到n的转移再复合一个0到$n\%m$的转移，这个东西可以在求0到n的转移的过程中顺带求出，总复杂度$O(n^2*logm)$