Description：

$N$ 个公交车站 $K$ 辆公交车， $1$ 到 $K$ 号站为始发站， $N-K+1$ 到 $N$ 号台为终点站，每个车站被经过一次，同一辆车相邻两个站间距离不超过 $P$ ，求方案数。

$1\leqslant n\leqslant 10^9,1\leqslant p\leqslant 10$

Solution：

发现实际上哪辆车怎么走是不重要的，只要把各个车区分出来就行了。

发现 $p$ 很小，可以把后几位的情况状压起来，要求状态有 $p$ 位，有 $k$ 个一，最后一位必须为 $1$ ，原因类似 $NOI$ 生成树计数那题，可以保证最后一个位置时一定有车，也就是说每向后一位就把一个车开到最后，然后构造矩阵快速幂即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<map>

#include<cctype>

#include<cstring>

using namespace std;

#define MOD 30031

int n,m,p;

#define MAXP 11

int state[1 << MAXP],tot = 0;

map<int,int> s;

struct matrix

{

	int m[200][200];

	matrix(){memset(m,0,sizeof(m));}

	friend matrix operator * (matrix a,matrix b)

	{

		matrix c;

		for(int i = 1;i <= tot;++i)

			for(int j = 1;j <= tot;++j)

		    	for(int k = 1;k <= tot;++k)

		      		c.m[i][j] = (c.m[i][j] + 1ll * a.m[i][k] * b.m[k][j] % MOD) % MOD;

		return c;

	}

	friend matrix operator ^ (matrix a,int b)

	{

		matrix res = a;--b;

		while(b > 0)

		{

			if(b & 1)res = res * a;

			a = a * a;

			b = b >> 1;

		}

		return res;

	}

}f;

int main()

{

	scanf("%d%d%d",&n,&m,&p);

	for(int b = 0;b < (1 << p);++b)

	{

		if((b & 1) == 0)continue;

		int cnt = 0,w = b;

		while(w > 0)

		{

			if(w & 1)++cnt;

			w = w >> 1;

		}

		if(cnt != m)continue;

		++tot;state[tot] = b;s[b] = tot;

	}

	for(int b = 1;b <= tot;++b)

	{

		int t;

		if(state[b] & (1 << (p - 1)))

		{

			t = ((state[b] << 1) & ((1 << p) - 1)) | 1;

			++f.m[s[state[b]]][s[t]];

		}

		else

		{

			for(int i = 1;i <= p;++i)

			{

				if(state[b] & (1 << (i - 1)))

				{

					t = ((state[b] ^ (1 << (i - 1))) << 1) | 1;

					++f.m[s[state[b]]][s[t]];

				}

			}

		}

	}

	matrix res = f ^ (n - m);

	cout << res.m[s[(1 << m) - 1]][s[(1 << m) - 1]] << endl;

	return 0;

}