[Solution][Dynamic Programming][Matrix Multiplication]SCOI2009 迷路

【题目】

戳这里

【思路】

考虑朴素的动态规划算法。

表示第i个时刻位置在j时的方法数。

考虑向后顺推,那么有

这样做完后就是答案。

不过时间复杂度为,时间空间都无法承受。

注意到如果把每个时刻视为一个阶段,每个阶段向后转移的规律是类似的,可以使用矩阵乘法优化。

做法是构造n行10列的矩阵,分别表示点0~n-1在时刻0~9时的方法数。再压成1行列的矩阵。

朴素Dp一次建立转移矩阵,进行T次矩阵乘法,使用快速幂优化。

时间复杂度.

【代码】

#include<cstdio>
#include<cstring>
const int mod = 2009;
int g[10][10];
struct Matrix
{
    int W , H;
    int d[100][100];
    Matrix()
    {
        W = H = 0;
        memset(d , 0 , sizeof(d));
    }
    void operator *= (const Matrix &b)
    {
        Matrix c;
        c.W = W , c.H = b.H;
        for(register int i = 0 ; i < c.W ; ++i)
        for(register int j = 0 ; j < c.H ; ++j)
        for(register int k = 0 ; k < H ; ++k)
        {
            c.d[i][j] = (c.d[i][j] + d[i][k] * b.d[k][j]) % mod;
        }
        *this = c;
    }
};
int main()
{
    int n , T;
    scanf("%d%d" , &n , &T);
    char s[31];
    register int i , j , k;
    for(i = 0 ; i < n ; ++i)
    {
        scanf("%s" , s);
        for(j = 0 ; j < n ; ++j)
            g[i][j] = s[j] - '0';
    }
    Matrix Add;
    Add.W = Add.H = 10 * n;
    for(i = 0 ; i < n ; ++i)
    for(k = 0 ; k < n ; ++k)
    {
            if (g[i][k])
                Add.d[i][n * (g[i][k] - 1) + k]++;
    }
    for(i = n ; i < 10 * n ; ++i)
        Add.d[i][i - n]++;
    Matrix Ans;
    Ans.W = 1 , Ans.H = 10 * n;
    Ans.d[0][0] = 1;
    while(T)
    {
        if (T & 1)
            Ans *= Add;
        Add *= Add;
        T >>= 1;
    }
    printf("%d" , Ans.d[0][n - 1]);
    return 0;
}
comments powered by Disqus