51nod1683

代码参考：http://blog.csdn.net/sdfzyhx/article/details/74359927

//dp[i][j][k]表示到了第i列，最下边的点最短路为j,剩下的点之间的关系为k的方案；

//只需知道这一行的棋盘状态和上一行的最短路之间的相对关系（1，0，-1）即可完成转移；

#include<iostream>

#include<cstring>

#include<cstdio>

#include<cmath>

#include<algorithm>

using namespace std;

const int max4=,max2=,maxm=,maxn=;

int transx[max4][max2],transy[max4][max2],dp[][maxm][max4],last[][maxm][max4];

int ans[maxm],f[maxn],tem[maxn],dis[maxn],quex[][],quey[][],n,m,p;

void update(int &x,int y){

    x+=y;

    x=(x>=p?x-p:x);

}

int main(){

    int x,y,x1,y1,ok,tl[];

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

    //预处理转移数组；

    for(int s=;s<(<<(*(n-)));++s){//上一行的最短路情况；

        ok=;

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

            x=(s>>((i-)*))&;

            if(x==){ok=;break;}

            if(x){

                if(x==)f[i]=f[i-]+;

                else f[i]=f[i-]-;

            }

            else f[i]=f[i-];

        }

        if(!ok)continue;

        for(int t=;t<(<<n);++t){//这一行的棋盘情况；

            for(int i=;i<n;++i)tem[i]=(t>>i)&;

            dis[]=f[]+tem[];

            for(int i=;i<n;++i)dis[i]=min(dis[i-],f[i])+tem[i];

            for(int i=n-;i>=;--i)dis[i]=min(dis[i],dis[i+]+tem[i]);

            transy[s][t]=dis[];

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

                if(dis[i]==dis[i-])x=;

                else if(dis[i]==dis[i-]+)x=;

                else x=;

                transx[s][t]|=x<<(*(i-));

            }

        }

    }

    //处理初始态；

    for(int t=;t<(<<n);++t){

        x=;

        for(int i=;i<n;++i)if((t>>i)&)x|=<<(*(i-));

        y=t&;

        if(last[][y][x])update(dp[][y][x],);

        else{

            last[][y][x]=;

            dp[][y][x]=;

            tl[]++;

            quex[][tl[]]=x;

            quey[][tl[]]=y;

        }

    }

    //转移

    for(int i=,c=;i<=m;++i,c^=){

        tl[c]=;

        for(int j=;j<=tl[c^];++j){

            x=quex[c^][j];

            y=quey[c^][j];

            for(int t=;t<(<<n);++t){

                x1=transx[x][t];

                y1=y+transy[x][t];

                if(last[c][y1][x1]==i)update(dp[c][y1][x1],dp[c^][y][x]);

                else{

                    last[c][y1][x1]=i;

                    dp[c][y1][x1]=dp[c^][y][x];

                    tl[c]++;

                    quex[c][tl[c]]=x1;

                    quey[c][tl[c]]=y1;

                }

            }

        }

    }

    //统计答案

    for(int j=;j<=tl[m&];++j){

        x=quex[m&][j];

        y1=y=quey[m&][j];

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

            x1=(x>>(*(i-)))&;

            if(x1==)y1++;

            else if(x1==)y1--;

        }

        update(ans[y1],dp[m&][y][x]);

    }

    for(int i=;i<n+m;++i)printf("%d\n",ans[i]);

    return ;

}