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

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

题目链接

题解:

先考虑最朴素的dp
(f[i][0/1])表示第(i)个位置跳/不跳的方案数,则:

[egin{cases} f[i][0]=f[i-1][0]+f[i-1][1]\ \ f[i][1]=f[i-m-1][0]+f[i-m-1][1] end{cases} ]

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

[g[i]=g[i-1]+g[i-m-1] ]

很明显可以用矩阵快速幂加速转移:
(g[i])可以转移至下一次的(g[i])
(g[i-m])可以转移至下一次的(g[i])
(g[i])可以转移至下一次的(g[i-1])
也就是说,构建一个这样的矩阵:

[G= left[ egin{matrix} 0&0&0&cdots&1\ 1&0&0&cdots&0\ 0&1&0&cdots&0\ 0&0&1&cdots&0\ &&vdots\ 0&0&0&cdots&1\ end{matrix} ight] ]

初始矩阵(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
",Ans);
	return 0;
}
原文地址:https://www.cnblogs.com/nianheng/p/10504877.html