hdu5318(2015 멀티 스쿨3)--The Goddess Of The Moon(dp+ 매트릭스 최적화)

제목 링크: 클릭하여 링크 열기
제목 대의: n가지 열을 제시합니다. 각 열은 무한한 여러 개가 있습니다. 지금 이 n가지 열 중에서 m개의 링크를 선택해야 합니다. 링크의 규칙은 a열의 접미사(len>=2)가 b열의 접미사이면 b를 a의 뒤로 받아서 최종적으로 몇 개의 다른 열을 구성할 수 있는지 물어보는 것입니다.
우선 중복된 것을 배제해야 한다. 중복된 것은 링크가 많이 생기지 않기 때문이다.그리고 i종 직렬에 대해 뒤에 몇 개의 직렬을 연결할 수 있는지 찾아내세요.
그리고 dp[i][j], i개의 열을 연결하면 j개의 열로 끝나는 것은 몇 가지입니다.이렇게 dp[i][j]=∑dp[i-1][k](k열 뒤에 j를 연결할 수 있음)
m<=1e9이기 때문에 매트릭스로 최적화합니다. 처음에 dp[1][i]는 모두 1이고 계산 매트릭스temp입니다.a[i][j], 만약 i번째 줄 뒤에 j를 연결할 수 있다면temp.[i][j]=1, 그렇지 않으면 0이다. 그러면 dp[i]와temp 행렬을 곱하면 dp[i+1]를 얻을 수 있다. 행렬의 빠른 멱을 사용하여 dp[1]*(temp.a)^(m-1)의 합을 계산한다.

#include <cstdio>
#include <cstring>
#include <stack>
#include <algorithm>
using namespace std ;
 #pragma comment(linker, "/STACK:1024000000,1024000000")
#define LL __int64
const int MOD = 1e9+7 ;
struct node{
    LL a[60][60] ;
};
char str[60][60] ;
LL a[60] , len[60] ;
stack<int> sta ;
int n ;
node mul(node p,node q) {
    int i , j , k ;
    node temp ;
    for(i = 0 ; i < n ; i++) {
        for(j = 0 ; j < n ; j++){
            temp.a[i][j] = 0 ;
            for(k = 0 ; k < n ; k++) {
                temp.a[i][j] = (temp.a[i][j] + p.a[i][k]*q.a[k][j]) % MOD ;
            }
        }
    }
    return temp ;
}
node pow(node p,int k) {
    node temp ;
    int i , j ;
    memset(temp.a,0,sizeof(temp.a)) ;
    for(i = 0 ; i < n ; i++) temp.a[i][i] = 1 ;
    while( k ) {
        if( k%2 ) temp = mul(temp,p) ;
        p = mul(p,p) ;
        k /=2 ;
    }
    return temp ;
}
int main() {
    int t , m ;
    int i , j , k , l ;
    node temp ;
    LL ans ;
    scanf("%d", &t) ;
    while( t-- ) {
        scanf("%d %d", &n, &m) ;
        for(i = 0 ; i < n ; i++)
            scanf("%I64d", &a[i]) ;
        sort(a,a+n) ;
        n = unique(a,a+n)-a;
        while( !sta.empty() ) sta.pop() ;
        for(i = 0 ; i < n ; i++) {
            do{
                sta.push(a[i]%10) ;
                a[i] /= 10 ;
            }while( a[i] ) ;
            len[i] = 0 ;
            while( !sta.empty() ) {
                str[i][ len[i]++ ] = sta.top()+'0' ;
                sta.pop() ;
            }
            str[i][ len[i] ] == '\0' ;
        }
        memset(temp.a,0,sizeof(temp.a)) ;
        for(i = 0 ; i < n ; i++) {
            for(j = 0 ; j < n ; j++) {
                for(l = 2 ; l <= len[i] && l <= len[j] ; l++) {
                    for(k = 0 ; k < l ; k++)
                        if( str[i][ len[i]-l+k ] != str[j][k] ) break ;
                    if( k >= l ){
                        temp.a[i][j] = 1 ;
                        break ;
                    }
                }
            }
        }
        temp = pow(temp,m-1) ;
        for(i = 0 , ans = 0 ; i < n ; i++){
            for(j = 0 ; j < n ; j++) {
                ans = (ans + temp.a[i][j]) % MOD ;
            }
        }
        printf("%I64d
", ans) ;
    }

}