team2012-F3-sol-0010

从 Trac 迁移的文章

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

原文章内容如下：

{{{
题意：一个k×n的矩形，里面有三种格子并且规定各自的走法，求从最左边任意一行走到最右边任意一行出来的方案数。
解法：由于有许多相同的列相邻，且k很小，可以用矩阵乘法解决，处理出每一种连续的情况下的单列方案数，再快速幂即可。
}}}
{{{
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long LL;

const int MOD = 11142457;
int n, k, m, type[10], plan[10][10];

struct mat
{
    LL dt[7][7];
    mat()
    {
        memset(dt, 0, sizeof(dt));
        for(int i=0;i<=k;i++)
            dt[i][i] = 1;
    }
    mat operator*(const mat& x)
    {
        mat res;
        memset(&res, 0, sizeof(res));
        for(int i=1;i<=k;i++)
            for(int j=1;j<=k;j++)
                for(int p=1;p<=k;p++)
                {
                    res.dt[i][j] += dt[i][p] * x.dt[p][j];
                    res.dt[i][j] %= MOD;
                }
        return res;
    }
    void operator*=(const mat& x)
    {
        (*this) = (*this) * x;
    }
    LL sum()
    {
        LL s = 0;
        for(int i=1;i<=k;i++)
            for(int j=1;j<=k;j++)
            {
                s += dt[i][j];
                s %= MOD;
            }
        return s;
    }
};

mat makemat()
{
    memset(plan, 0, sizeof(plan));
    for(int i=1;i<=k;i++)
    {
        if(type[i] == 1)
            plan[i][i]++;
        else if(type[i] == 2)
        {
            for(int j=i-1;j>=1;j--)
            {
                if(type[j] == 0)
                    break;
                if(type[j] == 2)
                {
                    plan[i][j]++;
                    break;
                }
            }
            for(int j=i+1;j<=k;j++)
            {
                if(type[j] == 0)
                    break;
                if(type[j] == 2)
                {
                    plan[i][j]++;
                    break;
                }
            }
        }
    }
    mat ret;
    for(int i=1;i<=k;i++)
        for(int j=1;j<=k;j++)
            ret.dt[i][j] = plan[i][j];
    return ret;
}

mat power(mat x, int p)
{
    mat ret;
    while(p)
    {
        if(p & 1)
            ret *= x;
        x *= x;
        p >>= 1;
    }
    return ret;
}

int main()
{
    while(~scanf("%d %d %d", &n, &k, &m))
    {
        mat ans;
        for(int i=1;i<=m;i++)
        {
            int t;
            scanf("%d", &t);
            for(int j=1;j<=k;j++)
                scanf("%d", &type[j]);

            ans *= power(makemat(), t);
        }
        printf("%lld\n", ans.sum());
    }
    return 0;
}
}}}

题意：一个k×n的矩形，里面有三种格子并且规定各自的走法，求从最左边任意一行走到最右边任意一行出来的方案数。
解法：由于有许多相同的列相邻，且k很小，可以用矩阵乘法解决，处理出每一种连续的情况下的单列方案数，再快速幂即可。

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long LL;
const int MOD = 11142457;
int n, k, m, type[10], plan[10][10];
struct mat
{
    LL dt[7][7];
    mat()
    {
        memset(dt, 0, sizeof(dt));
        for(int i=0;i<=k;i++)
            dt[i][i] = 1;
    }
    mat operator*(const mat& x)
    {
        mat res;
        memset(&res, 0, sizeof(res));
        for(int i=1;i<=k;i++)
            for(int j=1;j<=k;j++)
                for(int p=1;p<=k;p++)
                {
                    res.dt[i][j] += dt[i][p] * x.dt[p][j];
                    res.dt[i][j] %= MOD;
                }
        return res;
    }
    void operator*=(const mat& x)
    {
        (*this) = (*this) * x;
    }
    LL sum()
    {
        LL s = 0;
        for(int i=1;i<=k;i++)
            for(int j=1;j<=k;j++)
            {
                s += dt[i][j];
                s %= MOD;
            }
        return s;
    }
};
mat makemat()
{
    memset(plan, 0, sizeof(plan));
    for(int i=1;i<=k;i++)
    {
        if(type[i] == 1)
            plan[i][i]++;
        else if(type[i] == 2)
        {
            for(int j=i-1;j>=1;j--)
            {
                if(type[j] == 0)
                    break;
                if(type[j] == 2)
                {
                    plan[i][j]++;
                    break;
                }
            }
            for(int j=i+1;j<=k;j++)
            {
                if(type[j] == 0)
                    break;
                if(type[j] == 2)
                {
                    plan[i][j]++;
                    break;
                }
            }
        }
    }
    mat ret;
    for(int i=1;i<=k;i++)
        for(int j=1;j<=k;j++)
            ret.dt[i][j] = plan[i][j];
    return ret;
}
mat power(mat x, int p)
{
    mat ret;
    while(p)
    {
        if(p & 1)
            ret *= x;
        x *= x;
        p >>= 1;
    }
    return ret;
}
int main()
{
    while(~scanf("%d %d %d", &n, &k, &m))
    {
        mat ans;
        for(int i=1;i<=m;i++)
        {
            int t;
            scanf("%d", &t);
            for(int j=1;j<=k;j++)
                scanf("%d", &type[j]);
            ans *= power(makemat(), t);
        }
        printf("%lld\n", ans.sum());
    }
    return 0;
}