欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

HDU 6185 && 2017广西邀请赛:Covering(矩阵快速幂)

程序员文章站 2022-06-04 15:45:34
...

HDU 6185 && 2017广西邀请赛:Covering(矩阵快速幂)


题意:

用1*2的骨牌铺满4*n的矩形总共有多种方法

经典题:可见骨牌铺方格的多种做法


因为宽只有4,考虑先求递推式,假设当前长度为x,有:

①长度为x-1的所有情况后面竖着放2个骨牌,f(x) += f(x-1)

②长度为x-2的所有情况后面横着放4个骨牌或者横着放2个,竖着放2个,而后者又有三种不同放法,f(x) += 4f(x-2)

③长度为x-3的所有情况后面横着放4个,竖着放2个,去掉和②重复的有2种情况,f(x) += 2f(x-3)

④长度为x-4的所有情况后面横着放6个,竖着放2个,去掉和②③重复的有3种情况,f(x) += 3f(x-4)

……(这里建议纸上画一画)

最后可以发现规律得到公式

HDU 6185 && 2017广西邀请赛:Covering(矩阵快速幂)

将f(n)和f(n-1)相加有

HDU 6185 && 2017广西邀请赛:Covering(矩阵快速幂)

这样就可以转成矩阵了

HDU 6185 && 2017广西邀请赛:Covering(矩阵快速幂)

然后就可以愉快的快速幂了


#include<stdio.h>
#include<string.h>
#define mod 1000000007
#define LL long long
LL q[6] = {0,5,2,1,1};
typedef struct
{
	LL i, j;
	LL a[6][6];
	void init()
	{
		memset(a, 0, sizeof(a));
		a[1][4] = a[2][1] = a[2][2] = a[3][1] = a[4][3] = 1;
		a[1][2] = 5;
	}
	void unit()
	{
		memset(a, 0, sizeof(a));
		for(i=1;i<=4;i++)
			a[i][i] = 1;
	}
}Matrix;
Matrix Jz;
Matrix Powto(Matrix p, LL k);
Matrix Jjcf(Matrix p1, Matrix p2);
int main(void)
{
	LL i, n, ans;
	while(scanf("%lld", &n)!=EOF)
	{
		if(n==1)
			printf("1\n");
		else if(n==2)
			printf("5\n");
		else
		{
			Jz.init();
			Jz = Powto(Jz, n-2);
			ans = 0;
			for(i=1;i<=4;i++)
				ans = (ans+q[i]*Jz.a[1][i])%mod;
			printf("%lld\n", ans);
		}
	}
	return 0;
}

Matrix Powto(Matrix p, LL k)
{
	Matrix E;
	E.unit();
	while(k)
	{
		if(k%2)
			E = Jjcf(E, p);
		p = Jjcf(p, p);
		k /= 2;
	}
	return E;
}

Matrix Jjcf(Matrix p1, Matrix p2)
{
	Matrix pe;
	LL i, j, k;
	memset(pe.a, 0, sizeof(pe.a));
	for(i=1;i<=4;i++)
	{
		for(j=1;j<=4;j++)
		{
			for(k=1;k<=4;k++)
				pe.a[i][j] = (pe.a[i][j]+p1.a[i][k]*p2.a[k][j])%mod;
		}
	}
	return pe;
}

相关标签: hduoj