【poj3420】递推式转矩阵乘法

历史性的时刻！！！

推了一晚上！和hyc一起萌萌哒地推出来了！！

被摧残蹂躏的智商啊！！！

然而炒鸡高兴！！

（请不要介意蒟蒻的内心独白。。）

设a[i]为扫到第i行时的方案数。

易知，对于一行1*4的格子，只有一种方案把它铺满。

首先，对于当前的第i行，如果它不和第i-1行有联系（也就是它是独立的一行），那么就有1*a[i-1]=a[i-1]种方案。

如果第i行和第i-1行有联系（2行间互相联系），那么共有一下四种方案：

如果第i行、第i-1行、第i-2行都有联系（3行间两两联系），那么共有两种方案（此图以及的轴对称图形）：

如果第i行、第i-1行、第i-2行、第i-3行都有联系（4行间两两联系），那么共有三种方案（上面两种方案加下面一种）：

……

一直递推下去，我们可以发现：

2行间相互联系 --> 4种方案

3行间相互联系 --> 2种方案

4行间相互联系 --> 3种方案

……

奇数行相互联系（n>2) --> 2种方案

偶数行相互联系（n>2) --> 3种方案

所以，我们可以得出：

a[i]=a[i-1]+4*a[i-2]+2*(a[i-3]+a[i-5]+……+a[(i&1)?0:1])+3*(a[i-4]+a[i-6]+……+a[(i&1)?1:0]);

设s=a[i-3]+a[i-5]+……+a[(i&1)?0:1]，t=a[i-4]+a[i-6]+……+a[(i&1)?1:0];

该递推式可以转化为矩阵乘法：

代码如下：

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<iostream>

using namespace std;

const int N=;

int Mod;

struct node{

    int s[][];

    int sx,sy;

};

node mult(node a,node b)

{

    node t;

    t.sx=a.sx;t.sy=b.sy;

    memset(t.s,,sizeof(t.s));

    for(int i=;i<=a.sx;i++)

        for(int j=;j<=b.sy;j++)

            for(int k=;k<=a.sx;k++)

            {

                t.s[i][j]+=(a.s[i][k]*b.s[k][j])%Mod;

                t.s[i][j]%=Mod;

            }

    return t;

}

void quickpow(int n)

{

    if(n==) {printf("0\n");return ;}

    node a;

    a.s[][]=%Mod,a.s[][]=%Mod,a.s[][]=%Mod,a.s[][]=%Mod;

    a.s[][]=%Mod,a.s[][]=%Mod,a.s[][]=%Mod,a.s[][]=%Mod;

    a.s[][]=%Mod,a.s[][]=%Mod,a.s[][]=%Mod,a.s[][]=%Mod;

    a.s[][]=%Mod,a.s[][]=%Mod,a.s[][]=%Mod,a.s[][]=%Mod;

    a.sx=;a.sy=;

    node b;

    b.s[][]=b.s[][]=b.s[][]=b.s[][]=%Mod;

    b.s[][]=b.s[][]=b.s[][]=%Mod;

    b.s[][]=b.s[][]=b.s[][]=%Mod;

    b.s[][]=b.s[][]=b.s[][]=%Mod;

    b.s[][]=b.s[][]=b.s[][]=%Mod;

    b.sx=;b.sy=;

    while(n)

    {

        if(n&) b = mult(a,b);

        a = mult(a,a);

        n>>=;

    }

    node c;

    c.sx=;c.sy=;

    c.s[][]=%Mod;c.s[][]=c.s[][]=c.s[][]=%Mod;

    c = mult(b,c);

    printf("%d\n",c.s[][]);

    return ;

}

int main()

{

    while()

    {

        int x;

        scanf("%d%d",&x,&Mod);

        if(x==) return ;

        quickpow(x);

    }

    return ;

}

巴特西

【poj3420】递推式转矩阵乘法

最新文章

热门文章