cfedu60D

链接

题意

        有魔法石,一个魔法石可以分解为m个普通石,一个魔法师(普通石)占的空间为1,如果一个魔法石一个魔法石往容器里面装,装的时候可以选择分解魔法石为普通石或不分解,询问有多少种方法恰好占满空间为n的容器?分解顺序不同视为方法不同。
        n<1e18

题解

        设:
        dp[i]为放满体积i的方案数
        dp[n]=dp[n-1]+dp[n-m],可以用矩阵快速幂加速