P3977 [TJOI2015]棋盘

题目

P3977 [TJOI2015]棋盘

分析

以为是个神题，其实是出题人题目描述有毒。

状态压缩+矩阵乘法优化dp。

每一个棋子是处在中间一行的。。

于是就很容易了，直接状态压缩，然后矩阵乘法维护转移即可。

代码

#include <bits/stdc++.h>
using namespace std;
template <typename T>
inline void read(T &x){
	x=0;char ch=getchar();bool f=false;
	while(!isdigit(ch)){if(ch=='-'){f=true;}ch=getchar();}
	while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	x=f?-x:x;
	return ;
}
template <typename T>
inline void write(T x){
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10^48);
	return ;
}
#define ll long long
const int N=260,INF=1e9+7;
int n,m,p,k,lim;
struct Matrix{
	unsigned int a[N][N];
	Matrix(){memset(a,0,sizeof(a));}
	inline Matrix operator * (const Matrix &B)const{
		Matrix C;
		for(int i=0;i<lim;i++){
			for(int k=0;k<lim;k++){
				unsigned int r=a[i][k];
				for(int j=0;j<lim;j++) C.a[i][j]=(C.a[i][j]+r*B.a[k][j]);
			}
		}
		return C;
	}
	inline Matrix operator + (const Matrix &B)const{
		Matrix C;
		for(int i=0;i<lim;i++) for(int j=0;j<lim;j++) C.a[i][j]=(a[i][j]+B.a[i][j]);
		return C;
	}
};
struct Vector{
	unsigned int a[N];
	Vector(){memset(a,0,sizeof(a));}
	friend inline Vector operator * (const Vector &A,const Matrix &B){
		Vector C;
		for(int i=0;i<lim;i++){
			for(int j=0;j<lim;j++) C.a[i]=(C.a[i]+A.a[j]*B.a[j][i]);
		}
		return C;
	}
};
int a[N][N];
inline Matrix QuickPow(Matrix x,ll y){
	Matrix res;
	for(int i=0;i<lim;i++) res.a[i][i]=1;
	while(y){
		if(y&1) res=res*x;
		x=x*x;
		y>>=1;
	}
	return res;
}
signed main(){
	read(n),read(m);
	read(p),read(k);
	for(int i=1;i<=3;i++){
		for(int j=1;j<=p;j++){
			read(a[i][j]);
		}
	}
	k++;
	Matrix trans;
	Vector dp;
	dp.a[0]=1;lim=(1<<m);
	for(int S1=0;S1<(1<<m);S1++){
		for(int S2=0;S2<(1<<m);S2++){
			bool fl=false;
			for(int i=1;i<=m;i++){
				if(!((S1>>(i-1))&1)) continue;
				for(int j=1;j<=p;j++) if(a[3][j]&&i-(k-j)>=1&&i-(k-j)<=m&&((S2>>(i-(k-j)-1))&1)) fl=true;
				for(int j=1;j<=p;j++) if(a[2][j]&&i-(k-j)>=1&&i-(k-j)<=m&&((S1>>(i-(k-j)-1))&1)&&j!=k) fl=true;
			}
			for(int i=1;i<=m;i++){
				if(!((S2>>(i-1))&1)) continue;
				for(int j=1;j<=p;j++) if(a[1][j]&&i-(k-j)>=1&&i-(k-j)<=m&&((S1>>(i-(k-j)-1))&1)) fl=true;
			}
			if(fl) continue;
			trans.a[S2][S1]=1;
		}
	}
	trans=QuickPow(trans,n);
	dp=dp*trans;
	unsigned int Ans=0;
	for(int i=0;i<lim;i++) Ans=(Ans+dp.a[i]);
	write(Ans);
	return 0;
}