hdu2604 递推转换矩阵快速幂

刚开始还以为用位运算与或几下几个循环就搞定了,算着算着发现不行........

还是一种固定的切题角度,我假设有长度为n,总的排列数位f(n),怎么算他呢?从后往前考虑,因为大多数情况,都是用前面的结果推后面的结果, 那么当第n位是m的时候,如果我知道f(n-1)等于多少,那么f(n-1)的排列+加一个m是不是就是f(n)的一部分解了? 对吧,以此类推, 当第n位为f的时候,可是fff,fmf不能连着那是不是就剩下ffm,fmm的情况了,对于前者ffm,由于不能凑成ffmf的情况,所以只能是f(n-4). 对于后者fmm,无论邻接m的是什么都不会冲突,所以有f(n-3).至此全了,第n位的所有情况都考虑到了,那么就算出了以下公式:

f(n)=f(n-1)+f(n-3)+f(n-4)

写出代码拍上去发现超时了..........莫办法只能矩阵优化一下看看了.

我们设有矩阵A 使 (f[n],f[n-1],f[n-2],f[n-3]) = (f[n-1],f[n-2],f[n-3],f[n-4])*A成立

求出A={{1,0,1,1},{1,0,0,0},{0,1,0,0},{0,0,1,0}}

所以有 (f[n],f[n-1],f[n-2],f[n-3])=(f[1],f[2],f[3],f[4])*A的n-4次幂

上代码

#include<cstdio>

#include<cstring>

#include<iostream>

using namespace std;

int answer[];

struct mac

{

    int m[][];

};

mac power(mac x,mac y,int p)

{

    mac temp;

    for(int i=;i<;i++)

    {

        for(int j=;j<;j++)

        {

            temp.m[i][j]=;

            for(int k=;k<;k++)

                temp.m[i][j]=(temp.m[i][j]+x.m[i][k]*y.m[k][j])%p;

        }

    }

    return temp;

}

void eachother(int n,int k)

{

    mac pri,unit;

    memset(unit.m,,sizeof(unit.m));

    memset(pri.m,,sizeof(pri.m));

    unit.m[][]=unit.m[][]=unit.m[][]=unit.m[][]=;

    pri.m[][]=pri.m[][]=pri.m[][]=pri.m[][]=pri.m[][]=pri.m[][]=;

    while(n)

    {

        if(n&)

        {

            unit = power(unit,pri,k);

        }

        pri = power(pri,pri,k);

        n >>= ;

    }

    int ans = (answer[]*unit.m[][]+answer[]*unit.m[][]+answer[]*unit.m[][]+answer[]*unit.m[][])%k;

    printf("%d\n",ans);

}

int main()

{

    int n,k;

    while(scanf("%d%d",&n,&k)!=EOF)

    {

        memset(answer,,sizeof(answer));

        answer[]=;

        answer[]=;

        answer[]=;

        answer[]=;

        if(n<=)

        {

            printf("%d\n",answer[n]%k);

        }

        else{

           eachother(n-,k);

        }

    }

    return ;

}

巴特西

hdu2604 递推转换矩阵快速幂

最新文章

热门文章