题目描述

输入

输出

样例输入

1 10000

3 10000

5 10000

0 0

样例输出

1

11

95

数据范围

每个测试点数据组数不超过10组

解法

状态压缩动态规划。

设f[i][j]表示第i行状态为j的方案数：

f[i][j]=sum(f[i−1][k])（其中j可以从k中转移过来）

预处理出所有转移合法的情况。

然后矩阵乘法优化即可。

代码

#include<iostream>

#include<stdio.h>

#include<math.h>

#include<string.h>

#include<algorithm>

#define ll long long

#define ln(x,y) ll(log(x)/log(y))

#define sqr(x) ((x)*(x))

using namespace std;

const char* fin="aP2.in";

const char* fout="aP2.out";

const ll inf=0x7fffffff;

const ll maxn=100007,maxk=1<<4;

ll n,m,i,j,k;

bool ok[maxk][maxk];

struct rect{

    ll data[maxk][maxk];

    void init(){

        memset(data,0,sizeof(data));

    }

    rect(){

        init();

    }

    rect operator *(const rect &b){

        rect c;

        ll i,j,k;

        for (i=0;i<maxk;i++)

            for (j=0;j<maxk;j++)

                for (k=0;k<maxk;k++){

                    c.data[i][k]=(c.data[i][k]+data[i][j]*b.data[j][k])%m;

                }

        return c;

    }

    void operator =(const rect &b){

        ll i,j;

        for (i=0;i<maxk;i++) for (j=0;j<maxk;j++) data[i][j]=b.data[i][j];

    }

    rect power(ll b){

        rect a=*this,c;

        ll i,j,k=0;

        while (b){

            if (b&1)

            {

                if (k) c=c*a;

                else{

                    k=1;

                    c=a;

                }

            }

            a=a*a;

            b>>=1;

        }

        return c;

    }

}a,b;

void init(){

    ll i,j,k;

    for (i=0;i<maxk;i++)

        for (j=0;j<maxk;j++){

            b.data[j][i]=1;

            for (k=1;k<=4;k++){

                if (j&(1<<(k-1))){

                    if (i&(1<<(k-1))){

                        if (k<4){

                            if (!((j&(1<<k)) && (i&(1<<k)))){

                                b.data[j][i]=0;

                                break;

                            }

                            k++;

                        }else{

                            b.data[j][i]=0;

                            break;

                        }

                    };

                }else{

                    if (!(i&(1<<(k-1)))){

                        b.data[j][i]=0;

                        break;

                    }

                }

            }

        }

}

int main(){

    init();

    while (1){

        scanf("%d%d",&n,&m);

        if (n==0) break;

        a.init();

        a.data[0][maxk-1]=1;

        a=a*b.power(n);

        printf("%d\n",a.data[0][maxk-1]);

    }

    return 0;

}

启发

矩阵乘法可以用来优化状态较少的滚动的状态压缩动态规划。