本想着做一下第九届河南省省赛题,结果被这个类似骨牌覆盖的题卡住了,队友然我去hihoCoder上老老实实把骨牌覆盖一、二、三做完,这题就没什么问题了。虽然很不情愿,但还是去见识了一下。

 骨牌覆盖问题主要解决用1*2的骨牌来覆盖K*N的棋盘,求有多少种覆盖方法。k一般在7以内。比如hihocoder #1143用1*2的骨牌覆盖2*N的棋盘,很明显是个斐波那契数列。hihocider#1151问题上升到用1*2的骨牌覆盖3*N的棋盘。再上升到#1162的k*N的棋盘。

 我们有一个2xN的长条形棋盘,然后用1x2的骨牌去覆盖整个棋盘。对于这个棋盘,一共有多少种不同的覆盖方法呢?

提示:骨牌覆盖

我们考虑在已经放置了部分骨牌(灰色)的情况下,下一步可以如何放置新的骨牌(蓝色):

骨牌覆盖问题总结!hihoCoder/ NYOJ-1273宣传墙1151-LMLPHP

最右边的一种情况是不可能发生的,否则会始终多一个格子没有办法放置骨牌。或者说灰色部分的格子数为奇数,不可能通过1x2个骨牌放置出来。

那么通过对上面的观察,我们可以发现:

在任何一个放置方案最后,一定满足前面两种情况。而灰色的部分又正好对应了长度为N-1和N-2时的放置方案。由此,我们可以得到递推公式:

f[n] = f[n-1] + f[n-2];

这个公式是不是看上去很眼熟?没错,这正是我们的费波拉契数列。

f[0]=1,f[1]=1,f[2]=2,...

由于本题N很大,所以利用矩阵快速幂来优化。

提示:如何快速计算结果

当N很小的时候,我们直接通过递推公式便可以计算。当N很大的时候,只要我们的电脑足够好,我们仍然可以直接通过递推公式来计算。

但是我们学算法的,总是这样直接枚举不是显得很Low么,所以我们要用一个好的算法来加速(装X)。

事实上,对于这种线性递推式,我们可以用矩阵乘法来求第n项。对于本题Fibonacci数列,我们希望找到一个2x2的矩阵M,使得(a, b) x M = (b, a+b),其中(a,
b)和(b, a+b)都是1x2的矩阵。

显然,只需要取M = [0, 1; 1, 1]就可以了:

骨牌覆盖问题总结!hihoCoder/ NYOJ-1273宣传墙1151-LMLPHP

进一步得到:

骨牌覆盖问题总结!hihoCoder/ NYOJ-1273宣传墙1151-LMLPHP

那么接下来的问题是,能不能快速的计算出M^n?我们先来分析一下幂运算。由于乘法是满足结合律的,所以我们有:

骨牌覆盖问题总结!hihoCoder/ NYOJ-1273宣传墙1151-LMLPHP

不妨将k[1]..k[j]划分的更好一点?

骨牌覆盖问题总结!hihoCoder/ NYOJ-1273宣传墙1151-LMLPHP

其中(k[1],k[2]...k[j])2表示将n表示成二进制数后每一位的数字。上面这个公式同时满足这样一个性质:

骨牌覆盖问题总结!hihoCoder/ NYOJ-1273宣传墙1151-LMLPHP

结合这两者我们可以得到一个算法:

1. 先计算出所有的{a^1, a^2, a^4 ... a^(2^j)},因为该数列满足递推公式,时间复杂度为O(logN)

2. 将指数n二进制化,再利用公式将对应的a^j相乘计算出a^n,时间复杂度仍然为O(logN)

则总的时间复杂度为O(logN)

这种算法因为能够在很短时间内求出幂,我们称之为“快速幂”算法。

   以上便是一个裸的矩阵快速幂求斐波那契第N项了。可参考:矩阵快速幂

#1151 : 骨牌覆盖问题·二

对于3xN的棋盘,使用1x2的骨牌去覆盖一共有多少种不同的覆盖方法呢?很显然N为奇数是不可能的。

提示:3xN骨牌覆盖

在2xN的骨牌覆盖问题中,我们有递推式子 (0,1)xM^n=(f[n-1],f[n])。

我们考虑能否在3xN的情况下找到同样的式子。

但在实际的推导过程可以发现,对于3xN的覆盖,对应的f数值公式比2xN复杂太多。我们需要换个角度来思考推导公式。



在我们放置骨牌的过程中,一定是放好一行之后再放置下一行。根据摆放的方式,可能会产生很多种不同的形状,而这些形状之间是否具有某些递推关系呢?

如果他们存在一定的递推关系,则我们可以根据第i行的方案数来推导第i+1行的方案数。这样一行一行推导,直到第N行时不就得到了我们要求的方案数了么?

那么来研究一下是否存在这样的推导公式吧



假设我们已经放好了一些骨牌,对于当前最后一列(第i列)骨牌,可能有8种情况:

骨牌覆盖问题总结!hihoCoder/ NYOJ-1273宣传墙1151-LMLPHP

对于上面这8种状态,我们用数字来标记它们。以有放置骨牌的格子为1,未放置为0,转化为2进制数

以最下面一行作为1,则有:

骨牌覆盖问题总结!hihoCoder/ NYOJ-1273宣传墙1151-LMLPHP

接下来考虑如何放置骨牌,我们先将棋盘旋转一下。假设我们正在放置第i行的骨牌,那么会有下面3种方式:

骨牌覆盖问题总结!hihoCoder/ NYOJ-1273宣传墙1151-LMLPHP

灰色表示已经有的骨牌,绿色表示新放置的骨牌。

每一种放置方法解释如下,假设当第i行的状态为x,第i-1行的状态为y:

  • 第i行不放置,则前一行必须有放置的骨牌。x对应二进制位为0,y对应二进制位为1。
  • 第i行竖放骨牌,则前一行必须为空。x对应二进制位为1,y对应二进制位为0。
  • 第i行横向骨牌,则前一行必须两个位置均有骨牌,否则会产生空位。x对应二进制位为1,y对应二进制位为1。

    举个例子:

    骨牌覆盖问题总结!hihoCoder/ NYOJ-1273宣传墙1151-LMLPHP

    对于第i行状态1,我们在第i+1行竖放两块骨牌之后便能到达状态6。

    但是在这之中需要注意会出现下面这种情况:

    骨牌覆盖问题总结!hihoCoder/ NYOJ-1273宣传墙1151-LMLPHP

    这种情况看似是从状态1变成了状态0,其实是不对的。它不满足我们约定的放置方法,本质是第i行的状态1变成了第i行的状态7,而实际上我们应该放置的是第i+1行。

    所以在枚举递推关系的时候一定要注意。

    通过枚举8种状态到8种状态的转移,我们可以得到一个8x8的矩阵M(空白的地方均为0):

    骨牌覆盖问题总结!hihoCoder/ NYOJ-1273宣传墙1151-LMLPHP

    m[i][j]表示从状态i变成状态j的方案数。



    现在我们有了M矩阵,接下来考虑边界情况。

    在2xN的骨牌覆盖中,有(0, 1)作为初始向量A,那么在3xN中初始向量A是如何呢?

    让我们先想想A向量所代表的含义。M矩阵表示状态到状态的转移,则A向量所表示的应该就是第0行各状态的方案数。

    同理,对于A * M^n所求出的结果则应该表示为第n行各种状态的方案数。

    那么A向量应该是多少呢?很显然,第0行在我们递推的过程中必须看作状态7才合理。故A向量表示为:

    {0, 0, 0, 0, 0, 0, 0, 1}

    而对于我们寻求的答案,自然也是第n行放置为状态7的方案数了。
    struct martix
    {
    ll a[9][9];
    };
    int n;
    martix mul(martix A,martix B)
    {
    martix res;
    memset(res.a,0,sizeof(res.a));
    for(int i=0; i<8; i++)
    for(int j=0; j<8; j++)
    for(int k=0; k<8; k++)
    res.a[i][j]=(res.a[i][j]+A.a[i][k]*B.a[k][j])%MOD;
    return res;
    }
    martix fast(martix tmp,int num)
    {
    martix res;
    memset(res.a,0,sizeof(res.a));
    for(int i=0; i<8; i++) res.a[i][i]=1;
    while(num)
    {
    if(num&1) res=mul(res,tmp);
    tmp=mul(tmp,tmp);
    num>>=1;
    }
    return res;
    }
    void solve()
    {
    martix res,ans;
    memset(res.a,0,sizeof(res.a));
    memset(ans.a,0,sizeof(res.a));
    for(int i=0; i<8; i++) res.a[7-i][i]=1;
    res.a[3][7]=res.a[6][7]=res.a[7][3]=res.a[7][6]=1;
    ans.a[0][7]=1;
    res=fast(res,n);
    ans=mul(ans,res);
    printf("%lld\n",ans.a[0][7]);
    }
    int main()
    {
    while(~scanf("%d",&n))
    {
    solve();
    }
    return 0;
    }
  • #1162 : 骨牌覆盖问题·三

    对于给定的K和N,我们需要去求KxN棋盘的覆盖方案数。棋盘宽度为k,长度为N。2≤K≤7,1≤N≤100,000,000

    提示:KxN骨牌覆盖

    在2xN的骨牌问题中,我们有答案的递推序列。f[n] = f[n-1]+f[n-2]。

    事实上在处理3xN的问题中,也有部分选手推导出了答案的递推序列。

    那么对于4xN,5xN,是否也存在答案的递推序列呢?有兴趣的选手不妨尝试推导一下。



    在上一期,也就是3xN问题中,我们介绍了根据状态来递推的方法。这种方法显然是通用性最好的,可以用来解决任何K值的覆盖。

    对于任意一个K值,我们每一行拥有的状态数量为2^K种。

    在K=3时,我们是通过手动来枚举的8种状态之间的递推关系。

    当K=4或者更大的时候,再通过手动枚举就显得不那么科学了,此时我们需要考虑如何用程序生成我们所需要的状态转移矩阵。



    让我们再回头看看我们上一期提示里面放置骨牌的约定:

    假设我们正在放置第i行的骨牌,那么会有下面3种方式:

    骨牌覆盖问题总结!hihoCoder/ NYOJ-1273宣传墙1151-LMLPHP

    灰色表示已经有的骨牌,绿色表示新放置的骨牌。

    每一种放置方法解释如下,假设当第i行的状态为x,第i-1行的状态为y:

  • 第i行不放置,则前一行必须有放置的骨牌。x对应二进制位为0,y对应二进制位为1。
  • 第i行竖放骨牌,则前一行必须为空。x对应二进制位为1,y对应二进制位为0。
  • 第i行横向骨牌,则前一行必须两个位置均有骨牌,否则会产生空位。x对应二进制位为1,y对应二进制位为1。

    既然有对应的二进制描述,那么上面三种方法就可以用程序语言解释为:
  • 第i行不放置:new_x = x << 1, new_y = (y << 1) + 1; 列数+1
  • 第i行竖放骨牌:new_x = (x << 1) + 1, new_y = y << 1; 列数+1
  • 第i行横向骨牌:new x = (x << 2) + 3, new_y = (y << 2) + 3; 列数+2

    通过迭代去枚举3种放置方法,当总的列数等于K时,此时的x便可由y转移过来。那么我们可以得到枚举放置的伪代码:

    DFS(x, y, col):

    If col == K

    d[y][x] = 1

    Return ;

    End

    DFS(x << 1, (y << 1) + 1, col + 1);

    DFS((x << 1) + 1, y << 1, col + 1);

    If col + 2 <= K

    DFS( (x << 2) + 3, (y << 2) + 3, col + 2 )

    End

    当我们得到对应的矩阵之后,剩下需要做的也就和上一期相同了。



    在某些题目中有可能会出现,N很小,K很大的情况。比如N=20,K=14这样的情况。

    考虑到N很小,我们可以不使用矩阵乘法,而直接采用f[i-1]到f[i]行的递推。时间复杂度也就转化为2^(2k)*N。

    但是状态数量为2^14,也就是16384种。若采用转移矩阵,肯定是无法储存的。而实际情况是在转移矩阵中1的数量并不多,所以我们可以考虑存储为(y,x)这样的二元组。在转移过程中只枚举合法的转移即可。

    若K再更大一点,比如K=20,产生的状态有可能连开数组存储都很吃力。这个时候我们也可以考虑在计算每一行时,直接通过dfs来进行转移,不储存转移关系。用时间来换取空间。

    struct martix
    {
    ll a[150][150];
    };
    int k,n;
    martix mul(martix A,martix B)
    {
    martix res;
    memset(res.a,0,sizeof(res.a));
    for(int i=0; i<130; i++)
    for(int j=0; j<130; j++)
    for(int k=0; k<130; k++)
    res.a[i][j]=(res.a[i][j]+A.a[i][k]*B.a[k][j])%MOD;
    return res;
    }
    martix fast(martix tmp,int num)
    {
    martix res;
    memset(res.a,0,sizeof(res.a));
    for(int i=0; i<130; i++) res.a[i][i]=1;
    while(num)
    {
    if(num&1) res=mul(res,tmp);
    tmp=mul(tmp,tmp);
    num>>=1;
    }
    return res;
    }
    void dfs(int x,int y,int num,martix &res)
    {
    if(num==k)
    {
    res.a[y][x]=1;
    return ;
    }
    dfs(x<<1,(y<<1)+1,num+1,res);//加减比左移优先级高
    dfs((x<<1)+1,y<<1,num+1,res);
    if(num+2<=k) dfs((x<<2)+3,(y<<2)+3,num+2,res);
    }
    void solve()
    {
    martix res;
    memset(res.a,0,sizeof(res.a));
    dfs(0,0,0,res);
    res=fast(res,n);
    printf("%lld\n",res.a[(1<<k)-1][(1<<k)-1]);
    }
    int main()
    {
    while(~scanf("%d%d",&k,&n))
    {
    solve();
    }
    return 0;
    }
  • 有了上面的基础,如何来解决第九届河南省省赛的那道类似骨牌覆盖问题呢。

    基于数据较小,队友是强行dp过去的,但对于我这种dp弱渣还是老老实实用矩阵快速幂来的更快些。

    宣传墙

    时间限制:1000 ms  |  内存限制:65535 KB
    难度:4

    一条4*N道路被分为左右两个矩形,然后用1*2的骨牌去覆盖,求各有多少种方法。很明显左边矩形是4*(M-1),右边矩形是4*(N-M-K+1)。其实根据骨牌覆盖三我们很容易得到k为4的系数矩阵。只需在上面的代码将k改为4即可。

    struct martix
    {
    ll a[150][150];
    };
    int k,n,m,kk;
    martix mul(martix A,martix B)
    {
    martix res;
    memset(res.a,0,sizeof(res.a));
    for(int i=0; i<16; i++)
    for(int j=0; j<16; j++)
    for(int k=0; k<16; k++)
    res.a[i][j]=(res.a[i][j]+A.a[i][k]*B.a[k][j])%MOD;
    return res;
    }
    martix fast(martix tmp,int num)
    {
    martix res;
    memset(res.a,0,sizeof(res.a));
    for(int i=0; i<16; i++) res.a[i][i]=1;
    while(num)
    {
    if(num&1) res=mul(res,tmp);
    tmp=mul(tmp,tmp);
    num>>=1;
    }
    return res;
    }
    void dfs(int x,int y,int num,martix &res,martix &ans)
    {
    if(num==k)
    {
    res.a[y][x]=1;
    ans.a[y][x]=1;
    return ;
    }
    dfs(x<<1,(y<<1)+1,num+1,res,ans);//加减比左移优先级高
    dfs((x<<1)+1,y<<1,num+1,res,ans);
    if(num+2<=k) dfs((x<<2)+3,(y<<2)+3,num+2,res,ans);
    }
    void solve()
    {
    k=4;
    martix res,ans;
    memset(res.a,0,sizeof(res.a));
    memset(ans.a,0,sizeof(ans.a));
    dfs(0,0,0,res,ans);
    res=fast(res,m-1);
    int ans1=res.a[15][15];
    ans=fast(ans,n-m-kk+1);
    int ans2=ans.a[15][15];
    printf("%d %d\n",ans1,ans2);
    }
    int main()
    {
    int t;
    scanf("%d",&t);
    while(t--)
    {scanf("%d%d%d",&n,&m,&kk);
    solve();
    }
    return 0;
    }

    本想着和队友探讨一下如果单位矩阵不是1*2的,而是2*3或者其它的怎么做,然而队友推翻了我这种想法,也许出题人不会这样出题。有兴趣可以一(不)起(惜)探(赐)讨(教)

    05-27 11:57