【题意】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
      
       #include
       
        #include
        
         using namespace std;const int N=520,MOD=30031;int n,k,p,tot,c[N][N],q[N*2],A[N][N],ANS[N][N];void multply(int a[N][N],int b[N][N]){    for(int i=1;i<=tot;i++){        for(int j=1;j<=tot;j++){            c[i][j]=0;            for(int k=1;k<=tot;k++){                c[i][j]=(c[i][j]+a[i][k]*b[k][j])%MOD;            }        }    }    for(int i=1;i<=tot;i++)for(int j=1;j<=tot;j++)b[i][j]=c[i][j];}int main(){    scanf("%d%d%d",&n,&k,&p);    for(int S=0;S<(1<
         
          >1;        for(int i=0;i
          
           <
           
            <
            
             <
             
              >=1; } s=(1<