Virtual Judge链接:https://vjudge.net/problem/POJ-3744

分析 : 转移方程就是很显然的一个递推,,但是坐标的范围有1e8,不能直接做,所以要优化,线性的递推用矩阵加速是很常见的方法,所以构造出矩阵乘法 ,递推的复杂度可以变为log级别,然后我们按mine位置分段,每两个mine之间矩阵递推一次,n次之后可以得到答案。
code: