team2012-E1-mysol-0010

从 Trac 迁移的文章

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

原文章内容如下：

{{{
/* 解题报告 //

给出一个 k 行 n 列的网格，每个格子有三种类型：墙、直通道、L 型通道
列一共有 m 组，在每组中，同一行的格子类型是相同的
你可以任意设定管道的旋转方向，并在左边缘上任选一个格子作为入口
问有多少种方案可以到达右边缘

显然，可以用 dp[i][j] 表示到达 i 行 j 列那个格子左边缘时的方案数
若 a[i][j] = 0，dp[i][j + 1] = 0
若 a[i][j] = 1，dp[i][j + 1] = dp[i][j]
若 a[i][j] = 2，dp[i][j + 1] = dp[x][j] + dp[y][j]
  其中 x < i，y > i，a[x][j] = a[y][j] = 2
  且 a[x + 1 .. i - 1] = a[i + 1 .. y - 1] = 1
  即第 i 行，第 x 行和第 y 行的那三个格子都为 L 型通道
  在 x 行和 y 行之间的其他格子都为直通道

写出上面的 dp 式可以发现，这种线性的式子可以用矩阵进行加速计算
于是把转移方程写到矩阵里然后去做就可以了

// By 猛犸也钻地 @ 2012.07.20 */
}}}

{{{
#include <cstdio>
#include <vector>
using namespace std;

class MatInt{
public:
    static const int MOD = 11142457;
    typedef long long LL;
    typedef vector<int> BAR;
    int n,m;
    vector<BAR> u;
    MatInt():n(),m(){}
    MatInt(int c):u(c,BAR(c)){for(n=m=c;c--;u[c][c]=1);}
    MatInt(int n, int m):n(n),m(m),u(n,BAR(m)){}
    BAR& operator [](int idx){return u[idx];}
    const BAR& operator [](int idx) const{return u[idx];}
    operator bool() const{return n && m;}
    MatInt& operator *=(const MatInt& c){return *this=*this*c;}
    MatInt operator ~() const{
        MatInt ret(m,n);
        for(int i=0;i<m;i++) for(int j=0;j<n;j++) ret[i][j]=u[j][i];
        return ret;
    }
    MatInt operator *(const MatInt& c) const{
        if(m!=c.n) return MatInt();
        MatInt ret(n,c.m),v=~c;
        for(int i=0;i<n;i++) for(int j=0;j<c.m;j++) for(int k=0;k<m;k++)
            ret[i][j]=(ret[i][j]+LL(u[i][k])*v[j][k])%MOD;
        return ret;
    }
    MatInt pow(LL e) const{
        if(n!=m) return MatInt();
        MatInt ret=n,c=*this;
        for(;e;e>>=1,c*=c) if(e&1) ret*=c;
        return ret;
    }
};

int main(){
    int n,m,c[10];
    long long x;
    while(scanf("%lld%d",&x,&m)==2){
        MatInt a(1,m);
        for(int i=0;i<m;i++) a[0][i]=1;
        scanf("%d",&n);
        while(n--){
            scanf("%lld",&x);
            for(int i=0;i<m;i++) scanf("%d",c+i);
            MatInt e(m,m);
            for(int i=0;i<m;i++){
                if(c[i]==1) e[i][i]=1;
                if(c[i]!=2) continue;
                int j=i,k=i;
                while(--j>=0 && c[j]==1);
                while(++k< m && c[k]==1);
                if(j>=0) e[i][j]=1;
                if(k <m) e[i][k]=1;
            }
            a*=e.pow(x);
        }
        int ans=0;
        for(int i=0;i<m;i++) ans=(ans+a[0][i])%a.MOD;
        printf("%d\n",ans);
    }
}
}}}

/* 解题报告 //
给出一个 k 行 n 列的网格，每个格子有三种类型：墙、直通道、L 型通道
列一共有 m 组，在每组中，同一行的格子类型是相同的
你可以任意设定管道的旋转方向，并在左边缘上任选一个格子作为入口
问有多少种方案可以到达右边缘
显然，可以用 dp[i][j] 表示到达 i 行 j 列那个格子左边缘时的方案数
若 a[i][j] = 0，dp[i][j + 1] = 0
若 a[i][j] = 1，dp[i][j + 1] = dp[i][j]
若 a[i][j] = 2，dp[i][j + 1] = dp[x][j] + dp[y][j]
  其中 x < i，y > i，a[x][j] = a[y][j] = 2
  且 a[x + 1 .. i - 1] = a[i + 1 .. y - 1] = 1
  即第 i 行，第 x 行和第 y 行的那三个格子都为 L 型通道
  在 x 行和 y 行之间的其他格子都为直通道
写出上面的 dp 式可以发现，这种线性的式子可以用矩阵进行加速计算
于是把转移方程写到矩阵里然后去做就可以了
// By 猛犸也钻地 @ 2012.07.20 */

#include <cstdio>
#include <vector>
using namespace std;
class MatInt{
public:
    static const int MOD = 11142457;
    typedef long long LL;
    typedef vector<int> BAR;
    int n,m;
    vector<BAR> u;
    MatInt():n(),m(){}
    MatInt(int c):u(c,BAR(c)){for(n=m=c;c--;u[c][c]=1);}
    MatInt(int n, int m):n(n),m(m),u(n,BAR(m)){}
    BAR& operator [](int idx){return u[idx];}
    const BAR& operator [](int idx) const{return u[idx];}
    operator bool() const{return n && m;}
    MatInt& operator *=(const MatInt& c){return *this=*this*c;}
    MatInt operator ~() const{
        MatInt ret(m,n);
        for(int i=0;i<m;i++) for(int j=0;j<n;j++) ret[i][j]=u[j][i];
        return ret;
    }
    MatInt operator *(const MatInt& c) const{
        if(m!=c.n) return MatInt();
        MatInt ret(n,c.m),v=~c;
        for(int i=0;i<n;i++) for(int j=0;j<c.m;j++) for(int k=0;k<m;k++)
            ret[i][j]=(ret[i][j]+LL(u[i][k])*v[j][k])%MOD;
        return ret;
    }
    MatInt pow(LL e) const{
        if(n!=m) return MatInt();
        MatInt ret=n,c=*this;
        for(;e;e>>=1,c*=c) if(e&1) ret*=c;
        return ret;
    }
};
int main(){
    int n,m,c[10];
    long long x;
    while(scanf("%lld%d",&x,&m)==2){
        MatInt a(1,m);
        for(int i=0;i<m;i++) a[0][i]=1;
        scanf("%d",&n);
        while(n--){
            scanf("%lld",&x);
            for(int i=0;i<m;i++) scanf("%d",c+i);
            MatInt e(m,m);
            for(int i=0;i<m;i++){
                if(c[i]==1) e[i][i]=1;
                if(c[i]!=2) continue;
                int j=i,k=i;
                while(--j>=0 && c[j]==1);
                while(++k< m && c[k]==1);
                if(j>=0) e[i][j]=1;
                if(k <m) e[i][k]=1;
            }
            a*=e.pow(x);
        }
        int ans=0;
        for(int i=0;i<m;i++) ans=(ans+a[0][i])%a.MOD;
        printf("%d\n",ans);
    }
}