BZOJ1344 [Baltic2007]Connected Points连点

最新推荐文章于 2018-11-25 10:12:55 发布

neither_nor

最新推荐文章于 2018-11-25 10:12:55 发布

阅读量551

点赞数

分类专栏： BZOJ 矩阵乘法

本文链接：https://blog.csdn.net/neither_nor/article/details/72723932

版权

BZOJ 同时被 2 个专栏收录

382 篇文章

订阅专栏

矩阵乘法

11 篇文章

订阅专栏

该博客介绍了如何使用一眼矩乘动态规划方法解决BZOJ1344题目中提到的连点问题。文章提到，最后一列有特定的两种情况，总共存在六种状态，通过瞎jb矩乘操作即可得出解决方案。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

一眼矩乘DP

我们发现最后一列一定有两个点可以向后伸展，剩下那个点要么已经被占用了要么还没被占用，也就是说一共有六种状态，瞎jb矩乘一下即可

#include<iostream>
#include<cstring>
#include<ctime>
#include<cmath>
#include<algorithm>
#include<iomanip>
#include<cstdlib>
#include<cstdio>
#include<map>
#include<bitset>
#include<set>
#include<stack>
#include<vector>
#include<queue>
using namespace std;
#define MAXN 1010
#define MAXM 1010
#define ll long long
#define eps 1e-8
#define MOD 1000000000
#define INF 1000000000
struct mat{
	int x[6][6];
	mat(){
		memset(x,0,sizeof(x));
	}
	friend mat operator *(const mat &x,const mat &y){
		int i,j,k;
		mat z;
		for(i=0;i<6;i++){
			for(j=0;j<6;j++){
				for(k=0;k<6;k++){
					(z.x[i][j]+=(ll)x.x[i][k]*y.x[k][j]%MOD)%=MOD;
				}
			}
		}
		return z;
	}
};
int n;
mat R,C,X;
int a[6][6]={
			{0,0,0,1,0,1},
			{1,2,1,1,1,1},
			{0,1,0,0,0,0},
			{1,2,1,1,1,1},
			{0,1,0,0,0,0},
			{1,2,1,1,1,1}
};
int main(){
	int i;
	scanf("%d",&n);
	for(i=0;i<6;i++){
		R.x[i][i]=1;
	}
	memcpy(X.x,a,sizeof(a));
	n-=2;
	C.x[0][1]=C.x[0][2]=C.x[0][4]=1;
	while(n){
		if(n&1){
			R=R*X;
		}
		X=X*X;
		n>>=1;
	}
	C=C*R;
	ll ans=(ll)C.x[0][0]*2+C.x[0][1]+C.x[0][3]+C.x[0][5];
	printf("%lld\n",ans%MOD);
	return 0;
}

/*

*/