【题意】n个点等距排列在长度为n-1的直线上，初始点1~k都有一辆公车，每辆公车都需要一些停靠点，每个点至多只能被一辆公车停靠，且每辆公车相邻两个停靠点的距离至多为p，所有公车最后会停在n-k+1~n。给定n,k,p，求满足要求的方案数%30031。n<=10^9，k<=p<=10。
【算法】状压DP+矩阵快速幂
【题解】开始没看到p<=10，其实很显然p>k的话第一车就不满足要求了。考虑相邻停靠点没有关键信息，只能状压。
因为车都是从头开到尾的，所以直接考虑i~i-p+1的公车停靠状态就行了（i-p和i的距离为p，也就是必须跳到i，因此考虑i-p没有意义）。
设$f[i][S]$表示考虑第i个位置（最快的车可能到i），i~i-p+1的公车停靠状态为S的方案数，并且强制S的最低位为1（从前往后从低到高）。
$$f[i][S]=\sum f[i-1][S']$$
将S右移一位，然后枚举0~p中没有1的位置插入一个1得到的就是合法的S‘，然后把所有状态放在矩阵中就可以快速幂n-k次了。
注意到S是有效状态当且仅当S中含有恰好k个1，所以预处理合法状态数是C(p,k)的，这样复杂度就可以保证了。
总复杂度O(C(p,k)^3*log n)。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=,MOD=;
int n,k,p,tot,c[N][N],q[N*],A[N][N],ANS[N][N];
void multply(int a[N][N],int b[N][N]){
for(int i=;i<=tot;i++){
for(int j=;j<=tot;j++){
c[i][j]=;
for(int k=;k<=tot;k++){
c[i][j]=(c[i][j]+a[i][k]*b[k][j])%MOD;
}
}
}
for(int i=;i<=tot;i++)for(int j=;j<=tot;j++)b[i][j]=c[i][j];
}
int main(){
scanf("%d%d%d",&n,&k,&p);
for(int S=;S<(<<p);S++)if(S&){
int num=;
for(int i=;i<p;i++)if(S&(<<i))num++;
if(num!=k)continue;
tot++;q[S]=tot;
}
for(int S=;S<(<<p);S++)if(q[S]){
int s=S>>;
for(int i=;i<p;i++)if(!(s&(<<i))&&q[s|(<<i)])A[q[S]][q[s|(<<i)]]=;//
}
n-=k;
int s=(<<k)-;
ANS[q[s]][]=;
while(n){
if(n&)multply(A,ANS);
multply(A,A);
n>>=;
}
s=(<<k)-;
printf("%d",ANS[q[s]][]);
return ;
}