Luogu

BZOJ

分析

数据范围暴露正解系列

状压DP+矩阵快速幂。

首先可以写一个暴力状压DP。

设$f[i][j]$表示当前是第$i$个车站，前面$p$个车站的状态为$j$的方案数。

这里的状态是指“是否是最后的停靠站”。

所有合法状态预处理出来，发现只有$120$个左右。

考虑怎么转移。每次相当于把原来的状态中抽出来一个$1$丢到当前位置，并将其它的$1$往左挪一位。

再然后，发现转移只和后面的$j$有关，然后就可以上矩阵快速幂了。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define cnt(x) (__builtin_popcount(x))
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int MOD=30031;

int S[1<<11],cnt=0;

struct Matrix {
    int s[150][150];
    Matrix() { memset(this->s,0,sizeof(this->s)); }
} M;

inline Matrix Mul(Matrix a,Matrix b) {
    Matrix c;
    for (re int i=1;i<=cnt;++i) {
        for (re int j=1;j<=cnt;++j) {
            c.s[i][j]=0;
            for (re int k=1;k<=cnt;++k)
                c.s[i][j]=(c.s[i][j]+a.s[i][k]*b.s[k][j]%MOD)%MOD;
        }
    }
    return c;
}

inline Matrix FastPow(Matrix a,int b) {
    Matrix c;
    for (re int i=1;i<=cnt;++i) c.s[i][i]=1;
    for (;b;b>>=1,a=Mul(a,a))
        if (b&1) c=Mul(c,a);
    return c;
}

int main() {
    int n=read(),k=read(),p=read();
    for (re int i=0;i<(1<<p);++i) //预处理合法状态
        if ((i&1)&&cnt(i)==k) S[++cnt]=i;
    for (re int i=1;i<=cnt;++i)
        for (re int j=1;j<=cnt;++j)
            if (cnt((S[i]<<1)&S[j])==k-1) M.s[j][i]=1;
    M=FastPow(M,n-k);
    printf("%d\n",M.s[1][1]);
    return 0;
}