题意：
$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$处)的车先走避免重复
发现状态形成一个图，建立状态之间的邻接矩阵，就可以矩乘来算了
状态最多有$inom{9}{5}=126$种，我$dfs$状态的时候省去了强制的$1$
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> 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<n;k++) for(int i=0;i<n;i++) if(a[i][k]) for(int j=0;j<n;j++) if(b[k][j]) mod(re[i][j]+=a[i][k]*b[k][j]%MOD); return re; } Matrix operator ^(Matrix a,int b){ Matrix re;int n=m; for(int i=0;i<n;i++) re[i][i]=1; for(;b;b>>=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 ",d,num,s); if(num==0) {st[m++]=s;return;} for(int i=d;i<p-1;i++) dfs(i+1,num-1,s|(1<<i)); } void build(){ for(int i=0;i<m;i++) for(int j=0;j<m;j++){ int s= st[i]^(st[j]>>1);//printf("build %d %d %d ",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<m;i++) printf("st %d %d ",i,st[i]); build(); //for(int i=0;i<m;i++) for(int j=0;j<m;j++) printf("%d%c",g[i][j],j==m-1?' ':' ');puts(""); Matrix a,t=g^(n-k); //for(int i=0;i<m;i++) for(int j=0;j<m;j++) printf("%d%c",t[i][j],j==m-1?' ':' ');;puts(""); a[0][0]=1; a=a*t; //for(int i=0;i<m;i++) for(int j=0;j<m;j++) printf("%d%c",a[i][j],j==m-1?' ':' ');puts(""); printf("%d",a[0][0]); }