题解：UVA11551 Experienced Endeavour

_Sorasaki_Hina_ · 2026-04-24 08:48:48 · 题解

矩阵加速就好了呀。

下面规定索引为 1 到 n。

我们可以构造初始矩阵 T 为 \begin{bmatrix}a_1\\a_2\\\vdots\\a_n\end{bmatrix}，尝试构造转移矩阵 A（n 行 n 列），则答案矩阵 ans=A^r \times T。

不难发现，对于 a_i 的转移，若存在 k 使 b_{i,k} = j，则 A_{i,j}=1；
否则 A_{i,j}=0。

直接对 A 加速就可以了。

注意多组数据。

#include<iostream>
#include<cstdio>
#include<cstring>
#define re register
#define endl '\n'
#define ll long long
#define ull unsigned long long
#define db double
#define fi const int&
#define fl const ll&
#define ful const ull&
#define fc const char&
#define fs const string&
#define debug() puts("I Love Hina Forever")
using namespace std ;
namespace IO {
    template<class T>inline void read(T &x){char c=getchar(),f=false;x=0;while(c<48||c>57) {f|=(c==45),c=getchar();}while(c>=48&&c<=57){x=(x<<3)+(x<<1)+(c^48),c=getchar();}if(f){x=~x+1;}}
    template<class T,class ...Arg>inline void read(T &x,Arg &...arg){read(x),read(arg...);}
    template<class T>inline void write(T x){if(x<0){putchar(45),x=~x+1;}if(x>9){write(x/10);}putchar(x%10|48);}
    template<class T>inline void write(T x,fc c){write(x),putchar(c);}
}using namespace IO ;
const int N = 52,p = 1000 ;
struct matrix {
    int n,m ;
    ll a[N][N] ;
    inline matrix () {memset(a,0,sizeof a) ;}
    inline void prepare (fi _n,fi _m) {n = _n,m = _m ;}
    inline void read (fi _n,fi _m) {
        n = _n,m = _m ;
        for (re int i = 1 ; i <= n ; ++i) {
            for (re int j = 1 ; j <= m ; ++j) IO::read(a[i][j]) ;
        }
    }
};
inline matrix operator * (matrix A,matrix B) {
    matrix C ;
    C.prepare(A.n,B.m) ;
    for (re int i = 1 ; i <= C.n ; ++i) {
        for (re int j = 1 ; j <= C.m ; ++j) {
            for (re int k = 1 ; k <= A.m ; ++k) (C.a[i][j] += A.a[i][k] * B.a[k][j] % p) %= p ;
        }
    }
    return C ;
}
inline matrix operator ^ (matrix A,ll k) {
    matrix ans ;
    ans.prepare(A.n,A.m) ;
    for (re int i = 1 ; i <= ans.n ; ++i) ans.a[i][i] = 1 ;
    while (k) {
        if (k & 1) ans = ans * A ;
        k >>= 1,A = A * A ;
    }
    return ans ;
}
int T,n,r ;
inline matrix f (fi x) {
    matrix A,ans ;
    ans.read(n,1) ;
    A.prepare(n,n) ;
    for (re int i = 1,k ; i <= n ; ++i) {
        read(k) ;
        for (re int j = 1,t ; j <= k ; ++j) {
            read(t),++t ;
            A.a[i][t] = 1 ;
        }
    }
    ans = (A ^ x) * ans ;
    return ans ;
}

int main () {
    read(T) ;
    while (T--) {
        read(n,r) ;
        matrix ans = f(r) ;
        for (re int i = 1 ; i <= ans.n ; ++i) write(ans.a[i][1],i == n ? endl : ' ') ;
    }
    return 0 ;
}