题目链接

题解

状压dp，记$f[i][S]$表示$[1,i-p]$的车都被安排好了，而$[i-p+1,i]$的车中，$S$中有$1$的位置都安排有车停，并且恰好只有$k$个位置安排了（就是$k$辆车安排到的最后一个站，按照定义，显然$k$辆车安排的终点站必定在$[i-p+1,i]$内），其他的都没有安排。为了防止重复统计，钦定$S$的最高位（$i-p+1$）必定为$1$。

转移的话就是，如果$f[i][S]$与$f[i-1][T]$，$T$中的所有$1$与$S$中的所有$1$能对应上，那么$f[i][S]$就可以从$f[i-1][T]$转移过来。

由于状态总数为(nn/2)\binom{n}{n/2}(n/2n​)（最大是126），因此可以用矩阵乘法加速转移。

代码

#include 
    
     #include 
     
       int read(){
      int x=0,f=1;  char ch=getchar();  while((ch<'0')||(ch>'9'))    {
          if(ch=='-')        {
              f=-f;        }      ch=getchar();    }  while((ch>='0')&&(ch<='9'))    {
          x=x*10+ch-'0';      ch=getchar();    }  return x*f;} const int maxm=126;const int mod=30031; struct matrix{
      int n,m,a[maxm+2][maxm+2];   matrix operator *(const matrix &other) const  {
        matrix res;    res.n=n;    res.m=other.m;    memset(res.a,0,sizeof res.a);    for(int i=1; i<=n; ++i)      {
            for(int j=1; j<=other.m; ++j)          {
                for(int k=1; k<=m; ++k)              {
                    res.a[i][j]=(res.a[i][j]+1ll*a[i][k]*other.a[k][j])%mod;              }          }      }    return res;  }}; int stand[maxm+2],n,p,k,tot;matrix start,trans,ans; matrix quickpow(matrix res,matrix a,int b){
      while(b)    {
          if(b&1)        {
              res=res*a;        }      a=a*a;      b>>=1;    }  return res;} int main(){
      n=read();  p=read();  k=read();  for(int i=1<<(k-1); i<1<