本文主要是介绍牛客小白月赛7 J 方格填色(状压DP+矩阵快速幂)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：https://www.nowcoder.com/acm/contest/190/J
题目大意：给一个m*n的方格，每个格子可以是黑色或白色，要求左右相邻两格不能同时为白色，且相邻两列不能全为黑色，问可以有几种情况数。
题目思路：由于数据范围1<=m<=5,1<=n<=1e18，所以很容易看出是状压dp。由于他要求的都是对于两列之间，也就是说行之间没有要求，所以我们只要在列之间进行转移即可。这里使用状态来表示每列的情况。用0表示黑色用1表示白色。那么由于左右相邻两格不能同时为白色，所以表示两种状态的十进制数进行与得到的结果需要为0，还有一个条件是相邻两列不能全为黑色，那么相邻两列中至少有一个状态非0。然后我们构造一个2^m*2^m的矩阵，行和列分别表示每种情况，然后数字中只有1和0，表示这两种状态可不可以进行转移。然后可以转移的乘以a[i-1][0],a[i-1][1]……a[i-1][2^m-1](竖着的)，就能获得a[i][0],a[i][1]……a[i][2^m-1](竖着的)表示第i列各种状态的情况个数。然后全部加起来就是答案了。
以下是代码：
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
const int MAXN = 1e5+5;
const int MOD = 1e9+7;
int t[32][32];
struct node
{int n,m,a[32][32];void operator*=(const node& y){memset(t,0,sizeof(t));int i,j,k;for(i=0;i<n;i++)for(k=0;k<m;k++)for(j=0;j<y.m;j++)t[i][j]=(t[i][j]+(ll)a[i][k]*y.a[k][j])%MOD;m=y.m;for(i=0;i<n;i++)for(j=0;j<m;j++)a[i][j]=t[i][j];}
}A,S,T;
int main(){int m;ll n;while(~scanf("%d%lld",&m,&n)){memset(A.a,0,sizeof(A.a));memset(S.a,0,sizeof(S.a));memset(T.a,0,sizeof(T.a));m=1<<m;A.n=A.m=S.n=S.m=T.n=m;T.m=1;rep(i,0,m-1){A.a[i][i]=1;T.a[i][0]=1;}rep(i,0,m-1){rep(j,0,m-1){if(!(i&j)&&(i|j)){S.a[i][j]=1;}}}for(n--;n;n>>=1,S*=S)if(n&1)A*=S;A*=T;ll ans=0;rep(i,0,m-1){ans=(ans+A.a[i][0])%MOD;}printf("%lld\n",ans);}return 0;
}
这篇关于牛客小白月赛7 J 方格填色(状压DP+矩阵快速幂)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
