2012-A3-0010

从 Trac 迁移的文章

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

原文章内容如下：

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

而且题目中的格子图，连续的若干列有重复性。

如果从左往右，可以经过一形直接通过

也可以经过一个L形再通过同一列连续的一形在经过一个L形向右。

从左往右只有以上两种方式。

剩下的就是利用连续的若干列有重复性

a[i][j],表示从第i行进，第j行出的方案数，如果只是一列就计算上述两种方式.

剩下的就是把每一列的矩阵a[i][j]乘起来即可，需要用快速幂算法加速..

{{{
#include<cstdio>
#include<cstring>
typedef unsigned num;
typedef unsigned long long ull;
const num mo = 11142457;
num a[6][6],b[6][6],tmp[6][6],ret[6][6],k;
ull t,n;
char s[8];
void mul(num z[][6],num x[][6],num y[][6]){
    memset(z,0,k*6<<2);
    for(num i=0;i<k;++i)
        for(num j=0;j<k;++j)
            for(num l=0;l<k;++l)
                z[i][j]= (z[i][j]+x[i][l]*(ull)y[l][j])%mo;
}
void mov(num dst[][6],num src[][6]){
    for(num i=0;i<k;++i)
        for(num j=0;j<k;++j)
            dst[i][j]=src[i][j];
}
void pow(ull x){
    if(x!=1llu){
        pow(x>>1);
        mul(tmp,b,b);
        if(x&1)mul(b,tmp,a);
        else mov(b,tmp);
    }else mov(b,a);
}
int main(){
    for(num m,ans;2==scanf("%llu%u",&n,&k);printf("%u\n",ans)){
        memset(ret,0,sizeof(ret));
        for(num i=0;i<k;++i)ret[i][i]=1;
        for(scanf("%u",&m);m--;){
            scanf("%llu",&t);
            for(num i=0;i<k;++i)scanf(" %c",s+i);
            memset(a,0,sizeof(a));
            for(num i=0;i<k;++i)
            if(s[i]!='0'){
                if(s[i]=='1'){
                    a[i][i]=1;continue;
                }else{
                    num j;
                    for(j=i-1;~j && s[j]=='1';--j);
                    if(~j&&s[j]=='2')a[i][j]=1;
                    for(j=i+1;j<k && s[j]=='1';++j);
                    if(j<k&&s[j]=='2')a[i][j]=1;
                }
            }
            pow(t);mul(tmp,ret,b);
            mov(ret,tmp);
        }
        for(num i=ans=0;i<k;++i)
            for(num j=0;j<k;++j)
                ans=(ans+ ret[i][j])%mo;
    }
}
}}}

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

而且题目中的格子图，连续的若干列有重复性。

如果从左往右，可以经过一形直接通过

也可以经过一个L形再通过同一列连续的一形在经过一个L形向右。

从左往右只有以上两种方式。

剩下的就是利用连续的若干列有重复性

a[i][j],表示从第i行进，第j行出的方案数，如果只是一列就计算上述两种方式.

剩下的就是把每一列的矩阵a[i][j]乘起来即可，需要用快速幂算法加速..

#include<cstdio>
#include<cstring>
typedef unsigned num;
typedef unsigned long long ull;
const num mo = 11142457;
num a[6][6],b[6][6],tmp[6][6],ret[6][6],k;
ull t,n;
char s[8];
void mul(num z[][6],num x[][6],num y[][6]){
    memset(z,0,k*6<<2);
    for(num i=0;i<k;++i)
        for(num j=0;j<k;++j)
            for(num l=0;l<k;++l)
                z[i][j]= (z[i][j]+x[i][l]*(ull)y[l][j])%mo;
}
void mov(num dst[][6],num src[][6]){
    for(num i=0;i<k;++i)
        for(num j=0;j<k;++j)
            dst[i][j]=src[i][j];
}
void pow(ull x){
    if(x!=1llu){
        pow(x>>1);
        mul(tmp,b,b);
        if(x&1)mul(b,tmp,a);
        else mov(b,tmp);
    }else mov(b,a);
}
int main(){
    for(num m,ans;2==scanf("%llu%u",&n,&k);printf("%u\n",ans)){
        memset(ret,0,sizeof(ret));
        for(num i=0;i<k;++i)ret[i][i]=1;
        for(scanf("%u",&m);m--;){
            scanf("%llu",&t);
            for(num i=0;i<k;++i)scanf(" %c",s+i);
            memset(a,0,sizeof(a));
            for(num i=0;i<k;++i)
            if(s[i]!='0'){
                if(s[i]=='1'){
                    a[i][i]=1;continue;
                }else{
                    num j;
                    for(j=i-1;~j && s[j]=='1';--j);
                    if(~j&&s[j]=='2')a[i][j]=1;
                    for(j=i+1;j<k && s[j]=='1';++j);
                    if(j<k&&s[j]=='2')a[i][j]=1;
                }
            }
            pow(t);mul(tmp,ret,b);
            mov(ret,tmp);
        }
        for(num i=ans=0;i<k;++i)
            for(num j=0;j<k;++j)
                ans=(ans+ ret[i][j])%mo;
    }
}