nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial

转移自老blog

cfedu60D

链接

http://codeforces.com/contest/1117/problem/D

题意

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

题解

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