程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> HDU 5411 CRB and Puzzle（矩陣快速冪+可達矩陣）

HDU 5411 CRB and Puzzle（矩陣快速冪+可達矩陣）

編輯：關於C++

HDU 5411

題意：

Count the number of different patterns by counting the number of different paths of length at most m-1.

思路：

其實這類問題就是求：
S=I+A+A2+...+Am
一般普適的計算方式是：
(AmS)=(AI0I)m∗(I0)
這樣做的好處是可以得到最後的矩陣S，然後求S的所有元素和即是答案-1（沒統計∅），不過這題n <= 50 ，矩陣大小可能會超過100*100，時間復雜度將達到O(N3logM)再加上數據有20組，會被卡常數TLE，但有一個辦法就是將矩陣乘法的取模操作從最內層移到第二層（因為mod只有2015，也就是說矩陣最大元素只有2014，最內層的乘法加法操作不會爆int），可以進行一定常數優化，，剛好可以卡著時間AC（大概480ms）

但是這題並不需要我們求出最後的加和矩陣S，僅需要它的各項元素和即可，那麼我們可以把這個矩陣簡化成這樣(假設鄰接是個四階矩陣)：
????????11A1100001????????m=????????a1a2Ama3a40000a5????????
ans=∑ni=1ai
這樣做就避免了空間的浪費，且保留下來了答案，當然這裡初始矩陣的最下面一行1也可以放去最上層，最左層，最右層，因為是計算Ak所有元素和，並無影響。
這種做法復雜度與之前一致，但因為矩陣大小降了近乎一半，耗時相對少了很多（大概93msAC）

代碼：

方法1：

/*
* @author FreeWifi_novicer
* language : C++/C
*/
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include

using namespace std;

#define clr( x , y ) memset(x,y,sizeof(x))
#define cls( x ) memset(x,0,sizeof(x))
#define mp make_pair
#define pb push_back
typedef long long lint;
typedef long long ll;
typedef long long LL;

const int maxn = 100 + 5 ;
const int mod = 2015 ;
struct Matrix {
    int n , m ;
    int a[maxn][maxn] ;
    Matrix( int n , int m ){
        this->n = n ;
        this->m = m ;
        cls(a) ;
    }
    Matrix operator * ( const Matrix &tmp ){
        Matrix res( n , tmp.m ) ;
        for( int i = 0 ; i < n ; i++ ){
            for( int j = 0 ; j < tmp.m ; j++ ){
                for( int k = 0 ; k < m ; k++ )
                    res.a[i][j] += a[i][k] * tmp.a[k][j] ;
                if( res.a[i][j] > mod ) res.a[i][j] %= mod ;
            }
        }
        return res ;
    }
};

void Matrix_print( Matrix x ){
    for( int i = 0 ; i < x.n ; i++ ){
        for( int j = 0 ; j < x.m ; j++ ){
            cout << x.a[i][j] << ' ';
        }
        cout << endl;
    }
    cout << endl ;
}
Matrix fast_pow( Matrix x , int n ){
    Matrix res( x.n , x.m ) ;
    for( int i = 0 ; i < x.n ; i++ ) res.a[i][i] = 1 ;
    while( n ){
        if( n & 1 )
            res = res * x ;
        n >>= 1 ;
        x = x * x ;
    }
    return res ;
}

int main(){
//  freopen(input.txt,r,stdin);
    int t  ; cin >> t ;
    while( t-- ){
        int n , m ;
        cin >> n >> m ;
        Matrix G( 2 * n , 2 * n ) ;
        for( int i = 0 ; i < n ; i++ ){
            int k ;
            scanf( %d , &k ) ;
            for( int j = 0 ; j < k ; j++ ){
                int tmp ;
                scanf( %d , &tmp ) ;
                G.a[i][tmp-1] = 1 ;
            }
        }
        for( int i = n ; i < 2 * n ; i++ ){
            G.a[i][i - n] = 1 ;
            G.a[i][i] = 1 ;
        }
        Matrix base( 2 * n , n ) ;
        for( int i = 0 ; i < n ; i++ )
            base.a[i][i] = 1 ;
        G = fast_pow( G , m  );
        //Matrix_print( G ) ;
        base = G * base ;
        //Matrix_print( base ) ;
        int ans = 0 ;
        for( int i = n ; i < 2 * n ; i++ )
            for( int j = 0 ; j < n ; j++ )
                ans += base.a[i][j] ;
        cout << ( ans + 1 ) % mod << endl ;
    }
    return 0;
}

方法2：

/*
* @author FreeWifi_novicer
* language : C++/C
*/
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include

using namespace std;

#define clr( x , y ) memset(x,y,sizeof(x))
#define cls( x ) memset(x,0,sizeof(x))
#define mp make_pair
#define pb push_back
typedef long long lint;
typedef long long ll;
typedef long long LL;

const int maxn = 100 + 5 ;
const int mod = 2015 ;
struct Matrix {
    int n , m ;
    int a[maxn][maxn] ;
    Matrix( int n , int m ){
        this->n = n ;
        this->m = m ;
        cls(a) ;
    }
    Matrix operator * ( const Matrix &tmp ){
        Matrix res( n , tmp.m ) ;
        for( int i = 0 ; i < n ; i++ ){
            for( int j = 0 ; j < tmp.m ; j++ ){
                for( int k = 0 ; k < m ; k++ )
                    res.a[i][j] += a[i][k] * tmp.a[k][j] ;
                if( res.a[i][j] > mod ) res.a[i][j] %= mod ;
            }
        }
        return res ;
    }
};

void Matrix_print( Matrix x ){
    for( int i = 0 ; i < x.n ; i++ ){
        for( int j = 0 ; j < x.m ; j++ ){
            cout << x.a[i][j] << ' ';
        }
        cout << endl;
    }
    cout << endl ;
}
Matrix fast_pow( Matrix x , int n ){
    Matrix res( x.n , x.m ) ;
    for( int i = 0 ; i < x.n ; i++ ) res.a[i][i] = 1 ;
    while( n ){
        if( n & 1 )
            res = res * x ;
        n >>= 1 ;
        x = x * x ;
    }
    return res ;
}

int main(){
//  freopen(input.txt,r,stdin);
    int t  ; cin >> t ;
    while( t-- ){
        int n , m ;
        cin >> n >> m ;
        Matrix G( n + 1 , n + 1 ) ;
        for( int i = 0 ; i < n ; i++ ) G.a[n][i] = 1 ;
        for( int i = 0 ; i < n ; i++ ){
            int k ;
            scanf( %d , &k ) ;
            for( int j = 0 ; j < k ; j++ ){
                int tmp ;
                scanf( %d , &tmp ) ;
                G.a[i][tmp-1] = 1 ;
            }
        }
        Matrix_print( G ) ;
        G = fast_pow( G , m );
        Matrix_print( G ) ;
        int ans = 0 ;
        for( int i = 0 ; i <= n ; i++ )
            ans += G.a[n][i] ;
        cout << ( ans ) % mod << endl ;
    }
    return 0;
}