ACdream 1214---矩阵连乘

Problem Description

You might have noticed that there is the new fashion among rich people to have their yards tiled with black and white tiles, forming a pattern. The company Broken Tiles is well known as the best tiling company in our region. It provides the widest choices of nice patterns to tile your yard with. The pattern is nice if there is no square of size 2 × 2, such that all tiles in it have the same color. So patterns on the figure 1 are nice, while patterns on the figure 2 are not.

ACdream 1214---矩阵连乘

The president of the company wonders whether the variety of nice patterns he can provide to the clients is large enough. Thus he asks you to find out the number of nice patterns that can be used to tile the yard of size N × M . Now he is interested in the long term estimation, so he suggests N ≤ 10100. However, he does not like big numbers, so he asks you to find the answer modulo P .

Input

The input file contains three integer numbers: N (1 ≤ N ≤ 10100), M (1 ≤ M ≤ 5) and P (1 ≤ P ≤10000).

Output

Write the number of nice patterns of size N × M modulo P to the output file.

Sample Input

2 2 5

3 3 23

Sample Output

4

0

Source

Andrew Stankevich Contest 1

Manager

mathlover

题意：给出一个n*m的矩阵(n <= 10^100, m <= 5)，对于2*2的子方格若全是黑色或全是白色的是非法的，用黑白两色去染n*m的方格，问共有多少种合法的染色方案。

思路：构造出转移矩阵，上一行向下一行的转移矩阵，因为m<=5，每行最多有32个状态，可以进行状态压缩构造出一个32*32的转移矩阵A，A[i][j] = 1表示上一行i状态可以向下一行的j状态转移，否则不能转移。要求最后的合法方案数，就再构造一个B矩阵，是一个32*1的矩阵，表示了到达第一行每一个状态的方案数。那么A*B就表示到达第二行每一个状态的方案数，以此类推，A^n-1 * B表示到达第n行每一个状态的合法方案数，那么所有状态对应方案数的和就是总的方案数。

代码如下：

#include <iostream>

#include <cstring>

#include <cstdio>

#include <cstdlib>

#include <algorithm>

using namespace std;

#define DIGIT   4      //四位隔开,即万进制

#define DEPTH   10000        //万进制

#define MAX     100+5    //题目最大位数/4，要不大直接设为最大位数也行

typedef int bignum_t[MAX+];

/************************************************************************/

/* 读取操作数，对操作数进行处理存储在数组里                             */

/************************************************************************/

int read(bignum_t a,istream&is=cin)

{

    char buf[MAX*DIGIT+],ch ;

    int i,j ;

    memset((void*)a,,sizeof(bignum_t));

    if(!(is>>buf))return  ;

    for(a[]=strlen(buf),i=a[]/-;i>=;i--)

    ch=buf[i],buf[i]=buf[a[]--i],buf[a[]--i]=ch ;

    for(a[]=(a[]+DIGIT-)/DIGIT,j=strlen(buf);j<a[]*DIGIT;buf[j++]='');

    for(i=;i<=a[];i++)

    for(a[i]=,j=;j<DIGIT;j++)

    a[i]=a[i]*+buf[i*DIGIT--j]-'' ;

    for(;!a[a[]]&&a[]>;a[]--);

    return  ;

}

void write(const bignum_t a,ostream&os=cout)

{

    int i,j ;

    for(os<<a[i=a[]],i--;i;i--)

    for(j=DEPTH/;j;j/=)

    os<<a[i]/j% ;

}

int comp(const bignum_t a,const bignum_t b)

{

    int i ;

    if(a[]!=b[])

    return a[]-b[];

    for(i=a[];i;i--)

    if(a[i]!=b[i])

    return a[i]-b[i];

    return  ;

}

int comp(const bignum_t a,const int b)

{

    int c[]=

    {

    }

    ;

    for(c[]=b;c[c[]]>=DEPTH;c[c[]+]=c[c[]]/DEPTH,c[c[]]%=DEPTH,c[]++);

    return comp(a,c);

}

int comp(const bignum_t a,const int c,const int d,const bignum_t b)

{

    int i,t=,O=-DEPTH* ;

    if(b[]-a[]<d&&c)

    return  ;

    for(i=b[];i>d;i--)

    {

        t=t*DEPTH+a[i-d]*c-b[i];

        if(t>)return  ;

        if(t<O)return  ;

    }

    for(i=d;i;i--)

    {

        t=t*DEPTH-b[i];

        if(t>)return  ;

        if(t<O)return  ;

    }

    return t> ;

}

/************************************************************************/

/* 大数与大数相加                                                       */

/************************************************************************/

void add(bignum_t a,const bignum_t b)

{

    int i ;

    for(i=;i<=b[];i++)

    if((a[i]+=b[i])>=DEPTH)

    a[i]-=DEPTH,a[i+]++;

    if(b[]>=a[])

    a[]=b[];

    else

    for(;a[i]>=DEPTH&&i<a[];a[i]-=DEPTH,i++,a[i]++);

    a[]+=(a[a[]+]>);

}

/************************************************************************/

/* 大数与小数相加                                                       */

/************************************************************************/

void add(bignum_t a,const int b)

{

    int i= ;

    for(a[]+=b;a[i]>=DEPTH&&i<a[];a[i+]+=a[i]/DEPTH,a[i]%=DEPTH,i++);

    for(;a[a[]]>=DEPTH;a[a[]+]=a[a[]]/DEPTH,a[a[]]%=DEPTH,a[]++);

}

/************************************************************************/

/* 大数相减(被减数>=减数)                                               */

/************************************************************************/

void sub(bignum_t a,const bignum_t b)

{

    int i ;

    for(i=;i<=b[];i++)

    if((a[i]-=b[i])<)

    a[i+]--,a[i]+=DEPTH ;

    for(;a[i]<;a[i]+=DEPTH,i++,a[i]--);

    for(;!a[a[]]&&a[]>;a[]--);

}

/************************************************************************/

/* 大数减去小数(被减数>=减数)                                           */

/************************************************************************/

void sub(bignum_t a,const int b)

{

    int i= ;

    for(a[]-=b;a[i]<;a[i+]+=(a[i]-DEPTH+)/DEPTH,a[i]-=(a[i]-DEPTH+)/DEPTH*DEPTH,i++);

    for(;!a[a[]]&&a[]>;a[]--);

}

void sub(bignum_t a,const bignum_t b,const int c,const int d)

{

    int i,O=b[]+d ;

    for(i=+d;i<=O;i++)

    if((a[i]-=b[i-d]*c)<)

    a[i+]+=(a[i]-DEPTH+)/DEPTH,a[i]-=(a[i]-DEPTH+)/DEPTH*DEPTH ;

    for(;a[i]<;a[i+]+=(a[i]-DEPTH+)/DEPTH,a[i]-=(a[i]-DEPTH+)/DEPTH*DEPTH,i++);

    for(;!a[a[]]&&a[]>;a[]--);

}

/************************************************************************/

/* 大数相乘，读入被乘数a，乘数b，结果保存在c[]                          */

/************************************************************************/

void mul(bignum_t c,const bignum_t a,const bignum_t b)

{

    int i,j ;

    memset((void*)c,,sizeof(bignum_t));

    for(c[]=a[]+b[]-,i=;i<=a[];i++)

    for(j=;j<=b[];j++)

    if((c[i+j-]+=a[i]*b[j])>=DEPTH)

    c[i+j]+=c[i+j-]/DEPTH,c[i+j-]%=DEPTH ;

    for(c[]+=(c[c[]+]>);!c[c[]]&&c[]>;c[]--);

}

/************************************************************************/

/* 大数乘以小数，读入被乘数a，乘数b，结果保存在被乘数                   */

/************************************************************************/

void mul(bignum_t a,const int b)

{

    int i ;

    for(a[]*=b,i=;i<=a[];i++)

    {

        a[i]*=b ;

        if(a[i-]>=DEPTH)

        a[i]+=a[i-]/DEPTH,a[i-]%=DEPTH ;

    }

    for(;a[a[]]>=DEPTH;a[a[]+]=a[a[]]/DEPTH,a[a[]]%=DEPTH,a[]++);

    for(;!a[a[]]&&a[]>;a[]--);

}

void mul(bignum_t b,const bignum_t a,const int c,const int d)

{

    int i ;

    memset((void*)b,,sizeof(bignum_t));

    for(b[]=a[]+d,i=d+;i<=b[];i++)

    if((b[i]+=a[i-d]*c)>=DEPTH)

    b[i+]+=b[i]/DEPTH,b[i]%=DEPTH ;

    for(;b[b[]+];b[]++,b[b[]+]=b[b[]]/DEPTH,b[b[]]%=DEPTH);

    for(;!b[b[]]&&b[]>;b[]--);

}

/**************************************************************************/

/* 大数相除,读入被除数a，除数b，结果保存在c[]数组                         */

/* 需要comp()函数                                                         */

/**************************************************************************/

void div(bignum_t c,bignum_t a,const bignum_t b)

{

    int h,l,m,i ;

    memset((void*)c,,sizeof(bignum_t));

    c[]=(b[]<a[]+)?(a[]-b[]+): ;

    for(i=c[];i;sub(a,b,c[i]=m,i-),i--)

    for(h=DEPTH-,l=,m=(h+l+)>>;h>l;m=(h+l+)>>)

    if(comp(b,m,i-,a))h=m- ;

    else l=m ;

    for(;!c[c[]]&&c[]>;c[]--);

    c[]=c[]>?c[]: ;

}

void div(bignum_t a,const int b,int&c)

{

    int i ;

    for(c=,i=a[];i;c=c*DEPTH+a[i],a[i]=c/b,c%=b,i--);

    for(;!a[a[]]&&a[]>;a[]--);

}

/************************************************************************/

/* 大数平方根，读入大数a，结果保存在b[]数组里                           */

/* 需要comp()函数                                                       */

/************************************************************************/

void sqrt(bignum_t b,bignum_t a)

{

    int h,l,m,i ;

    memset((void*)b,,sizeof(bignum_t));

    for(i=b[]=(a[]+)>>;i;sub(a,b,m,i-),b[i]+=m,i--)

    for(h=DEPTH-,l=,b[i]=m=(h+l+)>>;h>l;b[i]=m=(h+l+)>>)

    if(comp(b,m,i-,a))h=m- ;

    else l=m ;

    for(;!b[b[]]&&b[]>;b[]--);

    for(i=;i<=b[];b[i++]>>=);

}

/************************************************************************/

/* 返回大数的长度                                                       */

/************************************************************************/

int length(const bignum_t a)

{

    int t,ret ;

    for(ret=(a[]-)*DIGIT,t=a[a[]];t;t/=,ret++);

    return ret>?ret: ;

}

/************************************************************************/

/* 返回指定位置的数字，从低位开始数到第b位，返回b位上的数               */

/************************************************************************/

int digit(const bignum_t a,const int b)

{

    int i,ret ;

    for(ret=a[(b-)/DIGIT+],i=(b-)%DIGIT;i;ret/=,i--);

    return ret% ;

}

/************************************************************************/

/* 返回大数末尾0的个数                                                  */

/************************************************************************/

int zeronum(const bignum_t a)

{

    int ret,t ;

    for(ret=;!a[ret+];ret++);

    for(t=a[ret+],ret*=DIGIT;!(t%);t/=,ret++);

    return ret ;

}

void comp(int*a,const int l,const int h,const int d)

{

    int i,j,t ;

    for(i=l;i<=h;i++)

    for(t=i,j=;t>;j++)

    while(!(t%j))

    a[j]+=d,t/=j ;

}

void convert(int*a,const int h,bignum_t b)

{

    int i,j,t= ;

    memset(b,,sizeof(bignum_t));

    for(b[]=b[]=,i=;i<=h;i++)

    if(a[i])

    for(j=a[i];j;t*=i,j--)

    if(t*i>DEPTH)

    mul(b,t),t= ;

    mul(b,t);

}

/************************************************************************/

/* 组合数                                                               */

/************************************************************************/

void combination(bignum_t a,int m,int n)

{

    int*t=new int[m+];

    memset((void*)t,,sizeof(int)*(m+));

    comp(t,n+,m,);

    comp(t,,m-n,-);

    convert(t,m,a);

    delete[]t ;

}

/************************************************************************/

/* 排列数                                                               */

/************************************************************************/

void permutation(bignum_t a,int m,int n)

{

    int i,t= ;

    memset(a,,sizeof(bignum_t));

    a[]=a[]= ;

    for(i=m-n+;i<=m;t*=i++)

    if(t*i>DEPTH)

    mul(a,t),t= ;

    mul(a,t);

}

#define SGN(x) ((x)>0?1:((x)<0?-1:0))

#define ABS(x) ((x)>0?(x):-(x))

int read(bignum_t a,int&sgn,istream&is=cin)

{

    char str[MAX*DIGIT+],ch,*buf ;

    int i,j ;

    memset((void*)a,,sizeof(bignum_t));

    if(!(is>>str))return  ;

    buf=str,sgn= ;

    if(*buf=='-')sgn=-,buf++;

    for(a[]=strlen(buf),i=a[]/-;i>=;i--)

    ch=buf[i],buf[i]=buf[a[]--i],buf[a[]--i]=ch ;

    for(a[]=(a[]+DIGIT-)/DIGIT,j=strlen(buf);j<a[]*DIGIT;buf[j++]='');

    for(i=;i<=a[];i++)

    for(a[i]=,j=;j<DIGIT;j++)

    a[i]=a[i]*+buf[i*DIGIT--j]-'' ;

    for(;!a[a[]]&&a[]>;a[]--);

    if(a[]==&&!a[])sgn= ;

    return  ;

}

struct bignum

{

    bignum_t num ;

    int sgn ;

    public :

    inline bignum()

    {

        memset(num,,sizeof(bignum_t));

        num[]= ;

        sgn= ;

    }

    inline int operator!()

    {

        return num[]==&&!num[];

    }

    inline bignum&operator=(const bignum&a)

    {

        memcpy(num,a.num,sizeof(bignum_t));

        sgn=a.sgn ;

        return*this ;

    }

    inline bignum&operator=(const int a)

    {

        memset(num,,sizeof(bignum_t));

        num[]= ;

        sgn=SGN (a);

        add(num,sgn*a);

        return*this ;

    }

    ;

    inline bignum&operator+=(const bignum&a)

    {

        if(sgn==a.sgn)add(num,a.num);

        else if

        (sgn&&a.sgn)

        {

            int ret=comp(num,a.num);

            if(ret>)sub(num,a.num);

            else if(ret<)

            {

                bignum_t t ;

                memcpy(t,num,sizeof(bignum_t));

                memcpy(num,a.num,sizeof(bignum_t));

                sub (num,t);

                sgn=a.sgn ;

            }

            else memset(num,,sizeof(bignum_t)),num[]=,sgn= ;

        }

        else if(!sgn)

            memcpy(num,a.num,sizeof(bignum_t)),sgn=a.sgn ;

        return*this ;

    }

    inline bignum&operator+=(const int a)

    {

        if(sgn*a>)add(num,ABS(a));

        else if(sgn&&a)

        {

            int  ret=comp(num,ABS(a));

            if(ret>)sub(num,ABS(a));

            else if(ret<)

            {

                bignum_t t ;

                memcpy(t,num,sizeof(bignum_t));

                memset(num,,sizeof(bignum_t));

                num[]= ;

                add(num,ABS (a));

                sgn=-sgn ;

                sub(num,t);

            }

            else memset(num,,sizeof(bignum_t)),num[]=,sgn= ;

        }

        else if

            (!sgn)sgn=SGN(a),add(num,ABS(a));

        return*this ;

    }

    inline bignum operator+(const bignum&a)

    {

        bignum ret ;

        memcpy(ret.num,num,sizeof (bignum_t));

        ret.sgn=sgn ;

        ret+=a ;

        return ret ;

    }

    inline bignum operator+(const int a)

    {

        bignum ret ;

        memcpy(ret.num,num,sizeof (bignum_t));

        ret.sgn=sgn ;

        ret+=a ;

        return ret ;

    }

    inline bignum&operator-=(const bignum&a)

    {

        if(sgn*a.sgn<)add(num,a.num);

        else if

        (sgn&&a.sgn)

        {

            int ret=comp(num,a.num);

            if(ret>)sub(num,a.num);

            else if(ret<)

            {

                bignum_t t ;

                memcpy(t,num,sizeof(bignum_t));

                memcpy(num,a.num,sizeof(bignum_t));

                sub(num,t);

                sgn=-sgn ;

            }

            else memset(num,,sizeof(bignum_t)),num[]=,sgn= ;

        }

        else if(!sgn)add (num,a.num),sgn=-a.sgn ;

        return*this ;

    }

    inline bignum&operator-=(const int a)

    {

        if(sgn*a<)add(num,ABS(a));

        else if(sgn&&a)

        {

            int  ret=comp(num,ABS(a));

            if(ret>)sub(num,ABS(a));

            else if(ret<)

            {

                bignum_t t ;

                memcpy(t,num,sizeof(bignum_t));

                memset(num,,sizeof(bignum_t));

                num[]= ;

                add(num,ABS(a));

                sub(num,t);

                sgn=-sgn ;

            }

            else memset(num,,sizeof(bignum_t)),num[]=,sgn= ;

        }

        else if

            (!sgn)sgn=-SGN(a),add(num,ABS(a));

        return*this ;

    }

    inline bignum operator-(const bignum&a)

    {

        bignum ret ;

        memcpy(ret.num,num,sizeof(bignum_t));

        ret.sgn=sgn ;

        ret-=a ;

        return ret ;

    }

    inline bignum operator-(const int a)

    {

        bignum ret ;

        memcpy(ret.num,num,sizeof(bignum_t));

        ret.sgn=sgn ;

        ret-=a ;

        return ret ;

    }

    inline bignum&operator*=(const bignum&a)

    {

        bignum_t t ;

        mul(t,num,a.num);

        memcpy(num,t,sizeof(bignum_t));

        sgn*=a.sgn ;

        return*this ;

    }

    inline bignum&operator*=(const int a)

    {

        mul(num,ABS(a));

        sgn*=SGN(a);

        return*this ;

    }

    inline bignum operator*(const bignum&a)

    {

        bignum ret ;

        mul(ret.num,num,a.num);

        ret.sgn=sgn*a.sgn ;

        return ret ;

    }

    inline bignum operator*(const int a)

    {

        bignum ret ;

        memcpy(ret.num,num,sizeof (bignum_t));

        mul(ret.num,ABS(a));

        ret.sgn=sgn*SGN(a);

        return ret ;

    }

    inline bignum&operator/=(const bignum&a)

    {

        bignum_t t ;

        div(t,num,a.num);

        memcpy (num,t,sizeof(bignum_t));

        sgn=(num[]==&&!num[])?:sgn*a.sgn ;

        return*this ;

    }

    inline bignum&operator/=(const int a)

    {

        int t ;

        div(num,ABS(a),t);

        sgn=(num[]==&&!num [])?:sgn*SGN(a);

        return*this ;

    }

    inline bignum operator/(const bignum&a)

    {

        bignum ret ;

        bignum_t t ;

        memcpy(t,num,sizeof(bignum_t));

        div(ret.num,t,a.num);

        ret.sgn=(ret.num[]==&&!ret.num[])?:sgn*a.sgn ;

        return ret ;

    }

    inline bignum operator/(const int a)

    {

        bignum ret ;

        int t ;

        memcpy(ret.num,num,sizeof(bignum_t));

        div(ret.num,ABS(a),t);

        ret.sgn=(ret.num[]==&&!ret.num[])?:sgn*SGN(a);

        return ret ;

    }

    inline bignum&operator%=(const bignum&a)

    {

        bignum_t t ;

        div(t,num,a.num);

        if(num[]==&&!num[])sgn= ;

        return*this ;

    }

    inline int operator%=(const int a)

    {

        int t ;

        div(num,ABS(a),t);

        memset(num,,sizeof (bignum_t));

        num[]= ;

        add(num,t);

        return t ;

    }

    inline bignum operator%(const bignum&a)

    {

        bignum ret ;

        bignum_t t ;

        memcpy(ret.num,num,sizeof(bignum_t));

        div(t,ret.num,a.num);

        ret.sgn=(ret.num[]==&&!ret.num [])?:sgn ;

        return ret ;

    }

    inline int operator%(const int a)

    {

        bignum ret ;

        int t ;

        memcpy(ret.num,num,sizeof(bignum_t));

        div(ret.num,ABS(a),t);

        memset(ret.num,,sizeof(bignum_t));

        ret.num[]= ;

        add(ret.num,t);

        return t ;

    }

    inline bignum&operator++()

    {

        *this+= ;

        return*this ;

    }

    inline bignum&operator--()

    {

        *this-= ;

        return*this ;

    }

    ;

    inline int operator>(const bignum&a)

    {

        return sgn>?(a.sgn>?comp(num,a.num)>:):(sgn<?(a.sgn<?comp(num,a.num)<:):a.sgn<);

    }

    inline int operator>(const int a)

    {

        return sgn>?(a>?comp(num,a)>:):(sgn<?(a<?comp(num,-a)<:):a<);

    }

    inline int operator>=(const bignum&a)

    {

        return sgn>?(a.sgn>?comp(num,a.num)>=:):(sgn<?(a.sgn<?comp(num,a.num)<=:):a.sgn<=);

    }

    inline int operator>=(const int a)

    {

        return sgn>?(a>?comp(num,a)>=:):(sgn<?(a<?comp(num,-a)<=:):a<=);

    }

    inline int operator<(const bignum&a)

    {

        return sgn<?(a.sgn<?comp(num,a.num)>:):(sgn>?(a.sgn>?comp(num,a.num)<:):a.sgn>);

    }

    inline int operator<(const int a)

    {

        return sgn<?(a<?comp(num,-a)>:):(sgn>?(a>?comp(num,a)<:):a>);

    }

    inline int operator<=(const bignum&a)

    {

        return sgn<?(a.sgn<?comp(num,a.num)>=:):(sgn>?(a.sgn>?comp(num,a.num)<=:):a.sgn>=);

    }

    inline int operator<=(const int a)

    {

        return sgn<?(a<?comp(num,-a)>=:):

        (sgn>?(a>?comp(num,a)<=:):a>=);

    }

    inline int operator==(const bignum&a)

    {

        return(sgn==a.sgn)?!comp(num,a.num): ;

    }

    inline int operator==(const int a)

    {

        return(sgn*a>=)?!comp(num,ABS(a)): ;

    }

    inline int operator!=(const bignum&a)

    {

        return(sgn==a.sgn)?comp(num,a.num): ;

    }

    inline int operator!=(const int a)

    {

        return(sgn*a>=)?comp(num,ABS(a)): ;

    }

    inline int operator[](const int a)

    {

        return digit(num,a);

    }

    friend inline istream&operator>>(istream&is,bignum&a)

    {

        read(a.num,a.sgn,is);

        return  is ;

    }

    friend inline ostream&operator<<(ostream&os,const bignum&a)

    {

        if(a.sgn<)

            os<<'-' ;

        write(a.num,os);

        return os ;

    }

    friend inline bignum sqrt(const bignum&a)

    {

        bignum ret ;

        bignum_t t ;

        memcpy(t,a.num,sizeof(bignum_t));

        sqrt(ret.num,t);

        ret.sgn=ret.num[]!=||ret.num[];

        return ret ;

    }

    friend inline bignum sqrt(const bignum&a,bignum&b)

    {

        bignum ret ;

        memcpy(b.num,a.num,sizeof(bignum_t));

        sqrt(ret.num,b.num);

        ret.sgn=ret.num[]!=||ret.num[];

        b.sgn=b.num[]!=||ret.num[];

        return ret ;

    }

    inline int length()

    {

        return :: length(num);

    }

    inline int zeronum()

    {

        return :: zeronum(num);

    }

    inline bignum C(const int m,const int n)

    {

        combination(num,m,n);

        sgn= ;

        return*this ;

    }

    inline bignum P(const int m,const int n)

    {

        permutation(num,m,n);

        sgn= ;

        return*this ;

    }

};

///=======================================================================================

const int MAXN = ;

const int MAXM = ;

int MOD;

typedef struct

{

    int mat[MAXN][MAXM];

}Matrix;

int kk;

Matrix Init(Matrix I)///单位矩阵

{

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

    {

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

        {

            if(i == j)

                I.mat[i][j] = ;

            else

                I.mat[i][j] = ;

        }

    }

    return I;

}

Matrix Multi_Matrix(Matrix a, Matrix b)///矩阵乘法

{

    Matrix c;

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

    {

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

        {

            c.mat[i][j] = ;

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

            {

                c.mat[i][j] += a.mat[i][k]*b.mat[k][j];

                c.mat[i][j] %= MOD;

            }

        }

    }

    return c;

}

int a[];

bool Judge_get_Binary(int i, int j)

{

    int cnt1=, cnt2=;

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

    {

        cnt1 = i%;

        cnt2 = j%;

        if(cnt1== && cnt2==)

            a[k] = ;

        else if(!cnt1 && !cnt2)

            a[k] = ;

        else

            a[k] = -;

        i/=, j/=;

    }

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

    {

        if(a[k]== && a[k+]==)

            return ;

        if(a[k]== && a[k+]==)

            return ;

    }

    return ;

}

Matrix BuildA()

{

    Matrix A;

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

    {

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

        {

            if(Judge_get_Binary(i, j))

                A.mat[i][j] = ;

            else

                A.mat[i][j] = ;

        }

    }

    return A;

}

int Eular(int m)   ///欧拉函数，本题没用上；

{

    int ans = m;

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

    {

        if(m%i==)

            ans = ans-ans/i;

        while(m%i==)

            m /= i;

    }

    if(m > )

        ans = ans-ans/m;

    return ans;

}

Matrix quick_MOD_Matrix(bignum n)

{

    n = n-;

    Matrix ans ;

    ans= Init(ans);

    Matrix A = BuildA();

    while(n>)

    {

        if(n%==)

            ans = Multi_Matrix(ans, A);

        n=n/;

        A = Multi_Matrix(A, A);

    }

    return ans;

}

int main()

{

    bignum n;

    while(cin>>n>>kk>>MOD)

    {

        Matrix tmp = quick_MOD_Matrix(n);

        Matrix ans;

        Matrix tmp1;

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

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

                tmp1.mat[i][j] = ;

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

        {

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

            {

                ans.mat[i][j] = ;

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

                {

                   ans.mat[i][j] += tmp.mat[i][k]*tmp1.mat[k][j];

                   ans.mat[i][j] %= MOD;

                }

            }

        }

        int sum = ;

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

        {

            sum = sum + ans.mat[i][];

            sum %= MOD;

        }

        sum = (sum%MOD+MOD)%MOD;

        cout<<sum<<endl;

    }

    return  ;

}

ACdream 1214---矩阵连乘的更多相关文章

ACdream - 1060 递推数(矩阵+循环节)
https://vjudge.net/problem/71677/origin 已知A(0) = 0 , A(1) = 1 , A(n) = 3 * A(n-1) + A(n-2) (n ≥ 2) 求 ...
hdu 1757 A Simple Math Problem (乘法矩阵)
A Simple Math Problem Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Ot ...
ACdream 1128 Maze（费用流）
题目链接:http://acdream.info/problem?pid=1128 Problem Description *qi陷入了一个迷宫中,这个迷宫是由N*M个格子组成的矩阵.每个格子上 ...
acdream 1222 Quantization Problem [dp]
称号:acdream 1222 Quantization Problem 题意:给出一个序列 a ,然后给出一个 n * m 的矩阵,让你从这个矩阵中选出一个序列k,使得sum(abs(ki - ai ...
ACM学习历程—SNNUOJ1214 矩阵1(二分)
题目链接:http://219.244.176.199/JudgeOnline/problem.php?id=1214 这是这次微软实习面试的一道题,题目大意就是:有一个n*m的矩阵,已知它每一行都是 ...
ACdream区域赛指导赛之专题赛系列(1)の数学专场
Contest : ACdream区域赛指导赛之专题赛系列(1)の数学专场 A:EOF女神的相反数题意:n(<=10^18)的数转化成2进制.翻转后(去掉前导零)输出十进制思路:water ...
ACDream手速赛2
地址:http://acdream.info/onecontest/1014 都是来自Codeforce上简单题. A. Boy or Girl 简单字符串处理 B. Walking in ...
C语言 &&num;183&semi; 矩阵乘法 &&num;183&semi; 算法训练
问题描述输入两个矩阵,分别是m*s,s*n大小.输出两个矩阵相乘的结果. 输入格式第一行,空格隔开的三个正整数m,s,n(均不超过200). 接下来m行,每行s个空格隔开的整数,表示矩阵A(i,j ...
获取Canvas当前坐标系矩阵
前言在我的另一篇博文 Canvas坐标系转换中,我们知道了所有的平移缩放旋转操作都会影响到画布坐标系.那在我们对画布进行了一系列操作之后,怎么再知道当前矩阵数据状态呢. 具体代码首先请看下面的一 ...

随机推荐

[LeetCode] Serialize and Deserialize Binary Tree 二叉树的序列化和去序列化
Serialization is the process of converting a data structure or object into a sequence of bits so tha ...
python 小程序查找最大的python文件
使用os.path模块方法介绍 1. 扫描标准库目录 I 通过glob模块遍历一个目录下面的所有文件,glob接收shell中常用文件名模式语法:"?"代表任何单个字符,* ...
【python】IP地址处理模块IPy
来源:https://pypi.python.org/pypi/IPy IPy模块该模块可以方便的处理IPv4和IPv6地址. 以下是从来源中拷贝的一些例子: >>> from I ...
Qt构建工具QBS之零 —— QBS 概览
本系列文章起因自己非常喜欢 QT 这个框架, 使用 QT 这几年, IDE 一直是使用的 QT 自带的 Qt Creator, 这个 IDE 本身比较轻巧, 同事相关的语法提示之类的也算够用, 但是 ...
PMBOK 项目管理九大知识领域和五大流程 PMI
Project Management Institute.PMI 是世界上最大的非盈利机构,是项目管理领域的领导者.PMI制定项目管理行业标准,带领项目管理的研究并提供项目管理的培训,证书,还有一些加 ...
阿里云直播SDK - &period;NET
阿里云sdk:https://develop.aliyun.com/sdk/csharp?spm=5176.doc27234.2.4.QiJb9l Github:https://github.com/ ...
PHP通过访客来路获取搜索关键词的方法
<?php class keyword{ public function getKeyword($referer){ if(strpos($referer,"http://www.ba ...
Day053--MySQL
MySQL安装和基本管理https://www.cnblogs.com/majj/p/9160383.html 管理员模式运行cmd 打开终端,输入mysqld,打开服务端. 打开终端,输入mysql ...
[Android Pro] so 动态加载—解决sdk过大问题
原文地址: https://blog.csdn.net/Rong_L/article/details/75212472 前言相信Android 开发中大家或多或少都会集成一些第三方sdk, 而其中难 ...
Solve error LNK2001 about pcl&colon;&colon;io&colon;&colon;vtkPolyDataToPointCloud
When use function 'pcl::io::vtkPolyDataToPointCloud' in PCL 1.6.0, one may have error as follows: &g ...