[HNOI2010]公交线路

题目

发现\(n\)比较大，但是\(k,p\)都很小，考虑矩乘使得复杂度倾斜一下

发现所有车的最大间隔都是\(p\)，还保证\(k<p\)，于是我们可以考虑压下最后\(p\)位的情况

于是设\(dp[i][S]\)表示目前最远的车来到了\(i\)位置，最后\(p\)为是否有车的状态是\(S\)，\(0\)表示没车，\(1\)表示有车

转移的话我们就使得某一辆车提前就好了，注意如果\(i-p+1\)有车的话，提前的只能是这辆车了

代码

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#define re register

const int M=1024;

const int mod=30031;

struct mat{int a[255][255];}a;

int n,K,P,sz;

int id[M],to[M];

inline mat operator*(mat a,mat b) {

	mat c;

	for(re int i=0;i<sz;i++)

		for(re int j=0;j<sz;j++) c.a[i][j]=0;

	for(re int k=0;k<sz;k++)

		for(re int i=0;i<sz;i++)

			for(re int j=0;j<sz;j++) {

				c.a[i][j]+=a.a[i][k]*b.a[k][j];

				if(c.a[i][j]>mod) c.a[i][j]%=mod;

			}

	return c;

}

mat ksm(int b) {

	mat S=a;b--;

	while(b) {if(b&1) S=S*a;b>>=1;a=a*a;}

	return S;

}

void dfs(int t,int s,int num) {

	if(t==P+1) {

		if(num==K) id[sz]=s,to[s]=sz++;

		return;

	}

	dfs(t+1,s,num);

	dfs(t+1,s|(1<<(t-1)),num+1);

}

int main() {

	scanf("%d%d%d",&n,&K,&P);

	dfs(1,0,0);

	for(re int i=0;i<sz;i++) {

		int now=id[i];

		for(re int j=0;j<P;j++)

		if(now>>j&1) {

			if((now>>(P-1)&1)&&j!=P-1) continue;

			a.a[to[(now^(1<<j))<<1|1]][i]++;

		}

	}

	int k=(1<<K)-1;

	mat ans=ksm(n-K);

	printf("%d\n",ans.a[to[k]][to[k]]);

	return 0;

}