题意：

$n$个公交站点，$k$辆车，$1...k$是起始站，$n-k+1..n$是终点站

每个站只能被一辆车停靠一次

每辆车相邻两个停靠位置不能超过$p$

求方案数

$n \le 10^9,\ p \le 8,\ k \le 10$

---

 

思考过程中遇到的主要问题是“所有车是同时前进的”，既不能单独考虑一辆车又没法考虑前面的车队后面的影响

正确的做法是同时考虑所有车

每$p$个位置一定每辆车各停一次

$f[i][s]$表示当前在站点$i$，且$i$有车，$s$为车停靠状态

强制规定最靠左(即$i$处)的车先走避免重复

发现状态形成一个图，建立状态之间的邻接矩阵，就可以矩乘来算了

 

状态最多有$\binom{9}{5}=126$种，我$dfs$状态的时候省去了强制的$1$

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;typedef long long ll;const int N=128,MOD=30031;inline int read(){    char c=getchar();int x=0,f=1;    while(c<'0'||c>'9'){
   if(c=='-')f=-1;c=getchar();}    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}    return x*f;}int n,k,p;struct Matrix{    int a[N][N];    int* operator [](int x){
   return a[x];}    Matrix(){memset(a,0,sizeof(a));}}g;int st[N],m;inline void mod(int &x){
   if(x>=MOD) x-=MOD;}Matrix operator *(Matrix a,Matrix b){    Matrix re;int n=m;    for(int k=0;k
          
           >=1,a=a*a) if(b&1) re=re*a; return re;}void dfs(int d,int num,int s){ //printf("Dfs %d %d %d\n",d,num,s); if(num==0) {st[m++]=s;return;} for(int i=d;i
           
            >1);//printf("build %d %d %d\n",st[i],st[j],s); if(s == (s&-s)) g[i][j]=1; }}int main(){ freopen("in","r",stdin); n=read();k=read();p=read(); dfs(0,k-1,0); //for(int i=0;i