注意到每個路線相鄰車站的距離不超過K，也就是說我們可以對連續K個車站的狀態進行狀壓。
然后狀壓DP一下，用矩陣快速冪加速運算即可。
?
#include <stdio.h> #include <stdlib.h> #include <string.h> #include <algorithm>#define MAXN 140 #define MOD 30031using namespace std;struct Matrix {int num[MAXN][MAXN];int n,m; //n*m大小矩陣void setOne(int a,int b){n=a,m=b;for(int i=1;i<=min(n,m);i++) num[i][i]=1;}Matrix() { memset(num,0,sizeof(num)); } }T,A,one;Matrix operator*(Matrix a,Matrix b) {Matrix c;c.n=a.n,c.m=b.m;for(int i=1;i<=c.n;i++)for(int j=1;j<=c.m;j++)for(int k=1;k<=a.m;k++)c.num[i][j]=(c.num[i][j]+a.num[i][k]*b.num[k][j])%MOD;return c; }Matrix fastPow(Matrix base,int pow) {Matrix ans;ans.setOne(base.n,base.m);while(pow){if(pow&1) ans=ans*base;base=base*base;pow>>=1;}return ans; }int calc(int x) //計算x的二進制中1的個數 {int sum=0;while(x){sum++;x-=x&(-x); //x去掉最后一個1 }return sum; }int n,k,p,goal; //goal是目標狀態bool canConvert(int to,int from) //檢查狀態from能否一步轉移到狀態to {from=(from-(1<<(p-1)))<<1; //這一步相當于把from向左推了一位，個位用0補齊int tmp=from^to; //tmp應該只有一個1if(tmp==(tmp&(-tmp))) return true; //tmp只有一個1，則是合法的return false; //否則是不合法的 }int status[MAXN],top=0; //保存所有DP過程中可能出現的狀態的棧int main() {scanf("%d%d%d",&n,&k,&p);for(int S=(1<<(p-1));S<(1<<p);S++) //枚舉DP狀態S,S是合法狀態當且僅當S的二進制中1的個數恰好為k {if(calc(S)==k){status[++top]=S;if(S==(1<<p)-1-((1<<(p-k))-1)) goal=top; //S是最終要達到的狀態 }}for(int i=1;i<=top;i++)for(int j=1;j<=top;j++)if(canConvert(status[i],status[j]))T.num[i][j]=1;A.n=A.m=T.n=T.m=top;A.num[1][goal]=1;T=fastPow(T,n-k);A=A*T;printf("%d\n",A.num[1][goal]);return 0; }
?
