POJ 3735 Training little cats (矩阵链乘应用)

给出n个猫,然后给出k个操作,依次执行这些操作,操作:1. 给猫i加一个坚果;2.猫i将自己的坚果吃完;3. 交换猫i和猫j的坚果。计算m轮k次操作后每个猫手里坚果的数量。

用矩阵竖向量表示每只猫拥有的坚果数量,考虑转移矩阵,操作1相当于矩阵平移,为了完成这个操作矩阵多设一维固定是1,操作2只需要将矩阵的整行赋0,操作3交换矩阵的i行和j行。这样就可以搞出k个矩阵连乘后的转移矩阵,接着只需要对转移矩阵m次幂即可。

 

LEAVE A COMMENT