[BZOJ4887/Luogu3758][TJOI2017]可乐(动态规划,矩阵快速幂)

发布于 2018-04-08  121 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ4887/Luogu3758][TJOI2017]可乐(动态规划,矩阵快速幂)

Description

加里敦星球的人们特别喜欢喝可乐。因而,他们的敌对星球研发出了一个可乐机器人,并且放在了加里敦星球的1号城市上。这个可乐机器人有三种行为: 停在原地,去下一个相邻的城市,自爆。它每一秒都会随机触发一种行为。现 在给加里敦星球城市图,在第0秒时可乐机器人在1号城市,问经过了t秒,可乐机器人的行为方案数是多少?

Tag

动态规划,矩阵快速幂

解决思路

每一次走都是一个类似计数动态规划的过程。发现每一次的转移其实是一样的,所以可以用矩阵快速幂优化转移。

代码

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ4887/Luogu3758][TJOI2017]可乐(动态规划,矩阵快速幂)


HNCJ OIer