首页 > 代码库 > 软件能力认证题---拼图(状态压缩DP+矩阵快速幂)
软件能力认证题---拼图(状态压缩DP+矩阵快速幂)
题意: 给定n*m的棋盘(1<=N<=10^15, 1<=M<=7),用L型骨牌(田字型任意去掉一个口)完全覆盖它,问有多少种解。
思路:m的范围只有1<=M<=7,显然状压DP。但是N的最大值到10^15,只能用快速幂了。
状态表示:0代表此处留空,1代表此处被填满。01序列压缩成一个int型来表示一行的填放情况。(例如:状态为4,则代表100,即第一列填满,第二第列三空)
边界条件:
其中,
t = 2^M
代表将前i-1行填满,且第i行放置了状态s时的总方案数。
代表上一行原本放置了状态s2的前提下,当前行放置骨牌把上一行填满并使得当前行状态为s1的方案数。
那么问题来了,怎么取得矩阵D呢?
我枚举上一行状态s2,对每个s2进行dfs:依次扫描s2的每一位,如果有空位置,则尝试拜访某个方向的骨牌(显然共4种方向)。当把s2所有位置摆满以后,s1便产生了,那么让增加1 (初始为0).
有了矩阵D,天黑都不怕!
显然有
矩阵快速幂即可,最后输出 就是结果。
题目本身没多难,都怪我状压DP没学好,做了这题总算弄明白了一些误区。
明明还有好多事情要忙,但是看到这种东西就是想做,好久没有这种纯粹的感觉了。。
下面附上代码
#include<cstdio> #include<cstring> #include<iostream> using namespace std; typedef long long LL; const int mod = 1000000007; const int maxn = 130; int off[5]={0,1,1,2,2}; int d[maxn][maxn]; LL N; int M; //N行 M列 int maxs; //总状态数 1<<M inline void int2arr(int num,bool arr[])//数字转矩阵 { for(int i=0;i<M;++i,num>>=1) arr[M-i-1] = num&1; } inline int arr2int(bool arr[])//矩阵转数字 { int num = 0; for(int i=0;i<M;(num<<=1)|=arr[i++]); return num; } bool sbuf[2][10]; inline bool check(int cur,int type)//判断在cur位置是否可以放置type方向的骨牌 { if(type == 1) return sbuf[0][cur]==0 && sbuf[1][cur]==0 && cur+1<M && sbuf[1][cur+1]==0; if(type == 2) return sbuf[0][cur]==0 && sbuf[1][cur]==0 && cur-1>=0 && sbuf[1][cur-1]==0; if(type == 3) return sbuf[0][cur]==0 && sbuf[1][cur]==0 && cur+1<M && sbuf[0][cur+1]==0; if(type == 4) return sbuf[0][cur]==0 && cur+1<M && sbuf[0][cur+1]==0 && sbuf[1][cur+1]==0; } inline void putblock(int cur,int type,int cont)//在cur位置放置type方向的骨牌 { if(type == 1) sbuf[1][cur] = sbuf[1][cur+1] = cont; if(type == 2) sbuf[1][cur] = sbuf[1][cur-1] = cont; if(type == 3) sbuf[1][cur] = cont; if(type == 4) sbuf[1][cur+1] = cont; } void dfs(int cur)//dfs不多解释 { if(cur >= M) { ++d[arr2int(sbuf[1])][arr2int(sbuf[0])]; return; } if(sbuf[0][cur]==1) dfs(cur+1);//如果当前位置已填,继续尝试下一列 for(int i=1;i<=4;++i) if(check(cur,i))//如果当前位置可以放置i方向骨牌 { putblock(cur,i,1);//尝试放置i方向骨牌 dfs(cur+off[i]);//继续尝试后面列 putblock(cur,i,0);//撤销放置i方向骨牌 } } inline void getd()//计算矩阵D { maxs = 1<<M; memset(d,0,sizeof(d)); for(int i=0;i<maxs;++i) int2arr(i,sbuf[0]), dfs(0); } inline void matmult(int a[maxn][maxn],int b[maxn][maxn])//矩阵乘法a*=b { static int c[maxn][maxn]; memset(c,0,sizeof(c)); for(int i=0;i<maxs;++i) for(int j=0;j<maxs;++j) for(int k=0;k<maxs;++k) c[i][j] = (c[i][j] + ((LL)a[i][k] * (LL)b[k][j]) % mod) % mod; memcpy(a,c,sizeof(c)); } void matpower(int a[maxn][maxn],LL p)//矩阵快速幂a^p { int ans[maxn][maxn]; memset(ans,0,sizeof(ans)); for(int i=0;i<maxs;++i) ans[i][i]=1; //ans=1 for(;p;p>>=1,matmult(a,a)) if(p&1) matmult(ans,a);//ans*=a; //a*=a; memcpy(a,ans,sizeof(ans)); //return ans } int main() { cin>>N>>M; getd(); matpower(d,N); cout<< d[ maxs-1 ][ maxs-1 ] <<endl; return 0; } /* 各个方向的骨牌及其对应编号 1 * ** 2 * ** 3 ** * 4 ** * */
软件能力认证题---拼图(状态压缩DP+矩阵快速幂)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。