Luogu-5004 专心OI-跳房子(矩阵快速幂)

题目链接

题解：

先考虑最朴素的dp

设\(f[i][0/1]\)表示第\(i\)个位置跳/不跳的方案数，则：

发现可以将\(f[i][0]+f[i][1]\)记为\(g[i]\)，上式化为

很明显可以用矩阵快速幂加速转移：

\(g[i]\)可以转移至下一次的\(g[i]\)

\(g[i-m]\)可以转移至下一次的\(g[i]\)

\(g[i]\)可以转移至下一次的\(g[i-1]\)

也就是说，构建一个这样的矩阵：

初始矩阵\(S[0][0]=1\)

代码：

#include<map>

#include<set>

#include<cmath>

#include<ctime>

#include<queue>

#include<stack>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define qmax(x,y) (x=max(x,y))

#define qmin(x,y) (x=min(x,y))

#define mp(x,y) make_pair(x,y)

using namespace std;

typedef long long ll;

typedef pair<int,int> pii;

inline ll read(){

	ll ans=0,fh=1;

	char ch=getchar();

	while(ch<'0'||ch>'9'){

		if(ch=='-') fh=-1;

		ch=getchar();

	}

	while(ch>='0'&&ch<='9')

		ans=ans*10+ch-'0',ch=getchar();

	return ans*fh;

}

const int P=1e9+7;

struct matrix{

	int a[20][20];

}S,G,base,Tmp;

int m;

ll n;

inline void build(){

	G.a[m][m]++,G.a[0][m]++;

	for(int i=1;i<=m;i++)

		G.a[i][i-1]++;

}

matrix operator * (matrix x,matrix y){

	for(int i=0;i<=m;i++)

		for(int j=0;j<=m;j++){

			Tmp.a[i][j]=0;

			for(int k=0;k<=m;k++)

				(Tmp.a[i][j]+=1ll*x.a[i][k]*y.a[k][j]%P)%=P;

		}

	return Tmp;

}

matrix poww(matrix x,ll y){

	for(int i=0;i<=m;i++)

		base.a[i][i]=1;

	while(y){

		if(y&1) base=base*x;

		x=x*x,y>>=1;

	}

	return base;

}

int main(){

//	freopen("nh.in","r",stdin);

//	freopen("zhy.out","w",stdout);

	n=read(),m=read();

	build(),G=poww(G,n+1);

	int Ans=0;

	for(int i=0;i<=m;i++)

		(Ans+=G.a[0][i])%=P;

	printf("%d\n",Ans);

	return 0;

}