【hdu6185】Covering（骨牌覆盖）

题意

题解

代码

代码语言：javascript复制

typedef long long ll;
typedef vector<ll> VI;
typedef vector<VI> Mat;
const ll mod=1000000007;
Mat mul(Mat &a,Mat &b){
	Mat c(SZ(a), VI(SZ(b[0])));
	rep(i,0,SZ(a))rep(j,0,SZ(b[0]))rep(k,0,SZ(b))
		c[i][j]=(c[i][j] a[i][k]*b[k][j])%mod;
	return c;
}
Mat qpow(Mat a,ll b){
	Mat c(SZ(a), VI(SZ(a)));
	rep(i,0,SZ(a))c[i][i]=1;
	for(;b;b>>=1,a=mul(a,a))if(b&1)c=mul(c,a);
	return c;
}

int main(){
	Mat a(4,VI(4));
	a[0]=VI{1,5,1,-1};
	rep(i,0,3)a[i 1][i]=1;
	ll n;
	while(~scanf("%lld",&n)){
		if(n==1)puts("1");
		else if(n==2)puts("5");
		else if(n==3)puts("11");
		else if(n==4)puts("36");
		else{
			Mat c=qpow(a,n-4);
			printf("%lldn",((c[0][0]*36 c[0][1]*11 c[0][2]*5 c[0][3])%mod mod)%mod);
		}
	}
	return 0;
}

状态压缩

代码语言：javascript复制

int main() {
	Mat a(6,VI(6));
	a[0]=VI{1,1,1,1,1,0};
	a[1]=VI{1,0,0,0,0,0};
	a[2]=VI{1,0,0,1,0,0};
	a[3]=VI{1,0,1,0,0,0};
	a[4]=VI{1,0,0,0,0,1};
	a[5]=VI{0,0,0,0,1,0};
	ll n;
	while(~scanf("%lld",&n)){
		printf("%lldn",qpow(a,n)[0][0]);
	}
	return 0;
}

骨牌覆盖 V2

代码语言：javascript复制

const int N=1<<5;
int n,m;
Mat a(N,VI(N));
void dfs(int c,int pre,int cur){
	if(c>n)return;
	if(c==n){
		  a[pre][cur];
		return;
	}
	dfs(c 1,pre<<1,cur<<1|1);//竖着放
	dfs(c 1,pre<<1|1,cur<<1);//不能放
	dfs(c 2,pre<<2,cur<<2);//横着放
}
int main() {
	while(~scanf("%d%d",&m,&n)){
		rep(i,0,SZ(a))rep(j,0,SZ(a[i]))a[i][j]=0;
		dfs(0,0,0);
		printf("%lldn",qpow(a,m)[0][0]);
	}
	return 0;
}

压缩

0 人点赞