搞了一个上午就搞出这一个题
还是看了题解的
不过还是看懂了。。而且自认为我比标程写的好懂些（事实上我都没看懂标程最后在干嘛）
首先观察数据范围：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]（每辆车都在终点站中）。
说点什么