题意：有n个公交车站，相邻站之间的距离为1km，有k辆公交车，1-k号站作为起始站，(n-k+1)-n作为终点站，每个站台必须且只能被一辆车经过，车只能从编号小的车站开往编号大的车站，一辆车一次最多开pkm，求所有车从起点站开往终点站的方案数
题解：
状压+矩阵快速幂
最原始的dp：dp[i][s]+=dp[j][s']
由于公交车的行驶距离不超过p，所以一定存在一个p位的状态能将k辆车表示出来
由于p和k很小，考虑状压
我们将所有可能的状态暴搜出来，并且发现这个可以用矩阵转移
然后构造转移矩阵，为了不重复计数，我们钦定每次只能移动第p位上的车然后判定两个状态之间能否转移（若何判定见代码注释）
然后转移矩阵转移(n-k)次（i从1到n-k+1），最后乘上初始矩阵即可
复杂度：O（log(n-k)*(C(9,4)^3)）
1 #include<iostream> 2 #include<cstdio> 3 #include<cstdlib> 4 #include<cstring> 5 #include<algorithm> 6 #include<cmath> 7 #define ll long long 8 #define mo 30031 9 #define lowbit(o) (o&(-o)) 10 using namespace std; 11 12 int n,k,p,cnt; 13 int g[130][130],v[130],bin[30]; 14 15 struct Mat { 16 int v[130][130]; 17 inline void mul(Mat x) { 18 memset(g,0,sizeof(g)); 19 for(int i=1; i<=cnt; i++) 20 for(int j=1; j<=cnt; j++) 21 for(int k=1; k<=cnt; k++) 22 (g[i][j]+=(v[i][k]*x.v[k][j])%mo)%=mo; 23 memcpy(v,g,sizeof(g)); 24 } 25 }ans,b; 26 27 int gi() { 28 int x=0,o=1; char ch=getchar(); 29 while(ch!='-' && (ch<'0' || ch>'9')) ch=getchar(); 30 if(ch=='-') o=-1,ch=getchar(); 31 while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar(); 32 return o*x; 33 } 34 35 void qpow(Mat &x, int y) { 36 Mat ret; 37 for(int i=1; i<=cnt; i++) ret.v[i][i]=1; 38 while(y) { 39 if(y&1) ret.mul(x); 40 x.mul(x),y>>=1; 41 } 42 x=ret; 43 } 44 45 void dfs(int now, int num, int sta) { 46 if(num==k) { 47 v[++cnt]=sta; 48 return; 49 } 50 for(int i=now-1; i>=1; i--) { 51 dfs(i,num+1,sta+bin[i-1]); 52 } 53 } 54 55 void pre() { 56 for(int i=1; i<=cnt; i++) 57 for(int j=1; j<=cnt; j++) { 58 int x=(v[i]<<1)^bin[p]^v[j];//v[i]<<1表示车的相对位置改变了，这样才能判定是否能转移到其他可行状态 59 if(x==lowbit(x))//判断是否只有p位上的车移动了 60 b.v[i][j]=1; 61 } 62 } 63 64 int main() { 65 n=gi(),k=gi(),p=gi(),bin[0]=1; 66 for(int i=1; i<=20; i++) bin[i]=bin[i-1]<<1; 67 dfs(p,1,bin[p-1]); 68 pre(); 69 qpow(b,n-k); 70 ans.v[1][1]=1; 71 ans.mul(b); 72 printf("%d", ans.v[1][1]); 73 return 0; 74 }