prow2012-A3-0010

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

题意是说，一个类似拨水管游戏的格子图，每一格有L形水管，一形水管，或者空，然后求从最左流到最右有几种方案，题目有一个重要限制：水不能往左流。 

首先能闻出这题是用矩阵乘法做DP，DP定义f[i][j]表示第i列的第j格冒出个插头的方案数有多少种，

那么，当某格为1时，它只能从f[i-1][j]转移；当某格为2时，它可以从上方和下方最近的一个2处转移。



{{{


#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <algorithm>
#include <set>
#include <map>
#include <sstream>
#include <string>
#include <math.h>
using namespace std;
#include <stdio.h>
#include <string.h>

struct Mat {
    long long M[6][6];

    void clear() {
        memset(M, 0, sizeof (M));
    }
};
int N, M, K;

void copy(Mat &A, Mat &B) {
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            A.M[i][j] = B.M[i][j];
}

void Mmut(Mat &A, Mat &B) {
    Mat C;
    int i, j, k;
    C.clear();
    for (i = 0; i < N; i++)
        for (j = 0; j < N; j++)
            if (A.M[i][j]) {
                for (k = 0; k < N; k++)
                {
                    C.M[i][k] += A.M[i][j] * B.M[j][k];
                    C.M[i][k]%=11142457;
                }
            }
    copy(A, C);
}
int main(){
    int i,j,a[100],k,P;
    while(scanf("%d%d",&M,&N)!=EOF){
        scanf("%d",&K);
        Mat init;
        init.clear();
        for (i=0;i<N;i++)
        init.M[0][i] = 1;
        for (i=0;i<K;i++){
            scanf("%d",&P);
            for (j=0;j<N;j++)
                scanf("%d",&a[j]);
            Mat round;
            round.clear();
            for (j=0;j<N;j++)
                if (a[j]==1)
                    round.M[j][j] = 1;
                else {
                    for (k=j-1;k>=0;k--)
                        if (a[k]==2) break;
                    if (k>=0) round.M[k][j] = 1;
                    for (k=j+1;k<N;k++)
                        if (a[k]==2) break;
                    if (k<N) round.M[k][j] = 1;
                }
            Mat res;
            res.clear();
            for (j=0;j<N;j++) res.M[j][j] = 1;
            while(P){
                if (P&1) Mmut(res,round);
                Mmut(round,round);
                P>>=1;
            }
            Mmut(init,res);
        }
        int res = 0;
        for (i=0;i<N;i++)
            res+=init.M[0][i],res%=11142457;
        printf("%d\n",res);
    }
}


}}}

题意是说，一个类似拨水管游戏的格子图，每一格有L形水管，一形水管，或者空，然后求从最左流到最右有几种方案，题目有一个重要限制：水不能往左流。

首先能闻出这题是用矩阵乘法做DP，DP定义f[i][j]表示第i列的第j格冒出个插头的方案数有多少种，

那么，当某格为1时，它只能从f[i-1][j]转移；当某格为2时，它可以从上方和下方最近的一个2处转移。

#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <algorithm>
#include <set>
#include <map>
#include <sstream>
#include <string>
#include <math.h>
using namespace std;
#include <stdio.h>
#include <string.h>
struct Mat {
    long long M[6][6];
    void clear() {
        memset(M, 0, sizeof (M));
    }
};
int N, M, K;
void copy(Mat &A, Mat &B) {
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            A.M[i][j] = B.M[i][j];
}
void Mmut(Mat &A, Mat &B) {
    Mat C;
    int i, j, k;
    C.clear();
    for (i = 0; i < N; i++)
        for (j = 0; j < N; j++)
            if (A.M[i][j]) {
                for (k = 0; k < N; k++)
                {
                    C.M[i][k] += A.M[i][j] * B.M[j][k];
                    C.M[i][k]%=11142457;
                }
            }
    copy(A, C);
}
int main(){
    int i,j,a[100],k,P;
    while(scanf("%d%d",&M,&N)!=EOF){
        scanf("%d",&K);
        Mat init;
        init.clear();
        for (i=0;i<N;i++)
        init.M[0][i] = 1;
        for (i=0;i<K;i++){
            scanf("%d",&P);
            for (j=0;j<N;j++)
                scanf("%d",&a[j]);
            Mat round;
            round.clear();
            for (j=0;j<N;j++)
                if (a[j]==1)
                    round.M[j][j] = 1;
                else {
                    for (k=j-1;k>=0;k--)
                        if (a[k]==2) break;
                    if (k>=0) round.M[k][j] = 1;
                    for (k=j+1;k<N;k++)
                        if (a[k]==2) break;
                    if (k<N) round.M[k][j] = 1;
                }
            Mat res;
            res.clear();
            for (j=0;j<N;j++) res.M[j][j] = 1;
            while(P){
                if (P&1) Mmut(res,round);
                Mmut(round,round);
                P>>=1;
            }
            Mmut(init,res);
        }
        int res = 0;
        for (i=0;i<N;i++)
            res+=init.M[0][i],res%=11142457;
        printf("%d\n",res);
    }
}