搞了一个上午就搞出这一个题
还是看了题解的
不过还是看懂了。。而且自认为我比标程写的好懂些(事实上我都没看懂标程最后在干嘛)
首先观察数据范围:109,显然得用O(n)以下复杂度的方法
那么就是什么logn了
一开始觉得是组合数学问题,然而发现并不能做
于是好像只有一种方法了:递推+矩阵快速幂
然而状态似乎不是很好搞。。
根据题解+用草稿纸推了半天。。。
———————————————————————————-
。。。。算了直接讲正解
首先定义状态dp[i][s]为走到第i位,状态为s的方案数
状态s的定义为每辆车到该点的距离的无序集合(可重复)
比如每辆车到这个点的距离分别为3,2,0,4
那么s为{0,2,3,4}
再证明一下:因为相邻站台有距离限制,所以s中的数只可能为[0,P)
并且因为该点所属车到该点的距离为0,所以s中必定有一个0
所以不同的s最多有max{C(p-1,k-1)}=C(9,5)=126种,就可以状态压缩了。
在定义一个矩阵m,当第i种状态能转移为第j种状态时m[i][j]=1,否则为0
规定第1种状态为{0,1,2,3…k-1},那么dp[k][1]=1(每辆车都在始发站中),dp[i]=dp[i-1]*m
矩阵快速幂,最终答案为dp[n][1](每辆车都在终点站中)。