[Solution][Dynamic Prigramming][Matrix Multiplication]ZJOI2004 沼泽鳄鱼

【题目】

戳这里

【思路】

想了好长时间的转移矩阵才想出来,果然是大Sate...

以时刻划分阶段按照点枚举向下转移的的朴素动态规划是很容易写出来的,但是显然会爆时空。

可以使用矩阵乘法优化。

由于每次转移到下一时刻的鳄鱼位置都有所不同,而他们的周期又很短,不妨取他们的最小公倍数12,形成一个大转移矩阵。

先构造前十二个时刻的转移矩阵,求出他们的积。

对于前的时刻的转移可以直接用积矩阵的次幂得出,剩下的用之前的小转移矩阵暴力转移。

时间复杂度.

【代码】

#include<cstdio>
#include<cstring>
const int Mo = 10000;
const int N = 50;
struct Matrix
{
    int W , H;
    int d[N][N];
    Matrix()
    {
        W = H = 0;
        memset(d , 0 , sizeof(d));
    }
    void set(int _W , int _H)
    {
        W = _W , H = _H;
    }
    void operator *= (const Matrix &b) 
    {
        Matrix c;
        c.set(W , b.H);
        register int i , j , k;
        for(i = 0 ; i < c.W ; ++i)
        for(j = 0 ; j < c.H ; ++j)
        for(k = 0 ; k < H ; ++k)
        {
            c.d[i][j] = (c.d[i][j] + d[i][k] * b.d[k][j]) % Mo;
        }
        *this = c;
    }
};
bool G[N][N] , None[12][N];
int Tmp[4];
int main()
{
    //freopen("tt.in" , "r" , stdin);
    int n , m , S , T , L;
    scanf("%d%d%d%d%d" , &n , &m , &S , &T , &L);
    register int i , j , k;
    int a , b;
    for(i = 0 ; i < m ; ++i)
    {
        scanf("%d%d" , &a , &b);
        G[a][b] = G[b][a] = 1;
    }
    int Nfish , Len;
    scanf("%d" , &Nfish);
    for(i = 0 ; i < Nfish ; ++i)
    {
        scanf("%d" , &Len);
        for(j = 0 ; j < Len ; ++j)
            scanf("%d" , &Tmp[j]);
        for(k = 0 , j = 0 ; k < 12 ; k++ , j = (j + 1) % Len)
            None[k][Tmp[j]] = 1;
    }
    Matrix Add[12];
    for(i = 0 ; i < 12 ; ++i)
    {
        Add[i].set(n , n);
        for(j = 0 ; j < n ; ++j)
        {
            //++Add[i].d[j][j];
            for(k = 0 ; k < n ; ++k)
            {
                if (G[j][k] && !None[(i + 1)%12][k])
                    ++Add[i].d[j][k];
            }
        }
    }
    Matrix Tot;
    Tot = Add[0];
    for(i = 1 ; i < 12 ; ++i)
        Tot *= Add[i];
    Matrix Ans;
    Ans.set(1 , n);
    Ans.d[0][S] = 1;
    for(int Time = L / 12; Time ; Time >>= 1)
    {
        if (Time & 1)
            Ans *= Tot;
        Tot *= Tot;     
    }
    int Last = L % 12;
    for(i = 0 ; i < Last ; ++i)
        Ans *= Add[i];
    printf("%d" , Ans.d[0][T]);
    return 0;
}
comments powered by Disqus