标签：状态压缩+矩阵快速幂。
题解：
首先看范围，p<=10，那么我们可以想到状态压缩。我们把从一个长度为10的区间进行压缩，1代表可以，那么当值一个区间的1的个数为k个，我们就认为他是合法的。要注意这里所定义的区间，是有起点的，但是没有记下来，因为没有必要。然后我们就可以想一下状态是怎么转移的。那么可行的状态有多少种呢?C(9，4)种。
然后两种状态是否能够转移是需要我们判断的，我们每次转移时只能移动一个公共汽车，并且是移动最前面的汽车，这样就可以避免重复统计的情况了前面说道区间是有起点的，那么这一区间的最前的汽车向后移动，对于后面的下一个状态来说，他的起点是向后移动了一格的，所以只需把后一个状态向前左移一位，再去判断是否有且仅有一个不同即可。
(这里有一个小技巧，那就是我们众所周知的树状数组的lowbit，(X & -X)代表的是X从右往左数的第一个1的位置，如100100就是位置3，那么返回2^2。所以利用这一点可以很好的判断一个数有多少个1，以及两个数是否仅仅相差一位不同。)
然后我们想想怎么办。我们每转移一个状态，就是移动一个汽车，那么初始时到结束时的状态就应该要移动n-k次。第一次汽车在起始站不要移动，后面要覆盖所有的车站就是n-k次，那么我们如过把状态看成一个点，能否转移看成一条边的话，一个很美妙的结论我们就可以使用了。
对于一个无权DAG，他的邻接矩阵的p次方就是两点直接距离为p的方案数。我们就这样使用矩阵快速幂，就可以统计出答案了。
终点状态:第n-k个车站为压缩状态的第一位，后面k位都是1。所以是1111110000(k个1，p-k个0)。起始状态是1000000000(其实按道理是1111110000，和终点状态一样，只是前面的i不同，省略了。)最后再使用初始矩阵去乘以转移矩阵的n-k次方就行了。
其实来说，对于初始矩阵×转移矩阵，这里是很鬼畜的，初始矩阵s[1][End]。最后查询s[1][End]。稍微算一算就可以发现，起始就是转移矩阵中的s[End][End]吧!所以也可以直接输出转移矩阵，这也是合情合理的。
1 #include<cstdio>
2 #include<iostream>
3 #include<algorithm>
4 using namespace std;
5 const int MAXN=150,mod=30031;
6 int n,p,k,top,END;
7 int que[MAXN];
8 struct ed
9 {
10 int s[MAXN][MAXN];
11 ed operator *(ed a)
12 {
13 ed b;
14 for(int i=1;i<=top;i++)
15 for(int j=1;j<=top;j++)
16 {
17 b.s[i][j]=0;
18 for(int k=1;k<=top;k++)
19 b.s[i][j]=(b.s[i][j]+s[i][k]*a.s[k][j])%mod;
20 }
21 return b;
22 }
23 }T,A;
24 ed pow(ed x,int p)
25 {
26 ed base=x;
27 p--;
28 while(p>0)
29 {
30 if(p&1)x=x*base;
31 base=base*base;
32 p/=2;
33 }
34 return x;
35 }
36 bool can(int x,int y)
37 {
38 y=(y-(1<<(p-1)))<<1;
39 int z=x^y;
40 if(z==(z&-z))return 1;
41 return 0;
42 }
43 int cal(int x)
44 {
45 int tot=0;
46 while(x>0)
47 {
48 x-=(x&-x);
49 tot++;
50 }
51 return tot;
52 }
53 int main()
54 {
55 cin>>n>>k>>p;
56 int L=1<<(p-1),R=(1<<p)-1,End=(1<<p)-1-(((1<<(p-k))-1));
57 for(;L<=R;L++)
58 {
59 if(cal(L)==k) que[++top]=L;
60 if(L==End) END=top;
61 }
62 for(int i=1;i<=top;i++)
63 for(int j=1;j<=top;j++)
64 if(can(que[i],que[j]))
65 T.s[i][j]=1;
66 T=pow(T,n-k);
67 A.s[1][END]=1;
68 A=A*T;
69 cout<<A.s[1][END]<<endl;
70 return 0;
71 }