题意：有若干字符，现在要把它们连成一个字符串，每种字符后面只能接特定种类的字符，现在询问能连接出的长度小于等于m的字符串有多少种。
思路：我们可以把这个转移关系看成一个图，如果字符a后面可以接b，那么从a向b连边。用邻接矩阵保存这个图。。。然后可以发现长度为m的字符串实际上是这个图中的一条长度为m（经过m个点）的路。那么可以想到一个经典结论：一个图中的k长路的条数等于这个图的邻接矩阵求k次幂后每项的和。
但是这样我们并不能直接得到答案，每次只能求出所有m长路。这里有个技巧，可以求出一个矩阵的1到m次幂的和。也就是A+A^2+A^3+....+A^m，这个和最后再求每一个元素的和就是答案了。
转移矩阵是这样的：
A 0
I I
这个矩阵直接求m次幂，用矩阵快速幂最终算法是O(n^3logm)的，最后左下角那个位置就是要求的幂和（可以手工验证下。。）
PS：比赛的时候把mod写在了三重循环里面，其实，这个2015的mod很有深意啊。。。把mod写到第二重循环里面就过了啊。。卧槽。取模这么慢。。
//#pragma comment(linker, "/STACK:102400000,102400000") #include <iostream> #include <map> #include <algorithm> #include <cstdio> #include <cstring> #include <cstdlib> #include <vector> #include <queue> #include <stack> #include <functional> #include <set> #include <cmath> #define pb push_back #define PB pop_back #define fs first //#define se second #define sq(x) (x)*(x) #define IINF (1<<29) using namespace std; typedef long long ll; typedef pair<ll,ll> P; const int mod=2015; int sz; int mid[110][110]; struct matrix{ int m[110][110]; matrix(){ memset(m,0,sizeof m); } void mul(const matrix &b){ memset(mid,0,sizeof mid); for(int i=0;i<sz;i++){ for(int j=0;j<sz;j++){ for(int k=0;k<sz;k++){ mid[i][j]=(mid[i][j]+m[i][k]*b.m[k][j]); } mid[i][j]%=mod; } } for(int i=0;i<sz;i++){ for(int j=0;j<sz;j++){ m[i][j]=mid[i][j]; } } } void selfmul(){ memset(mid,0,sizeof mid); for(int i=0;i<sz;i++){ for(int j=0;j<sz;j++){ for(int k=0;k<sz;k++){ mid[i][j]=(mid[i][j]+m[i][k]*m[k][j]); } mid[i][j]%=mod; } } for(int i=0;i<sz;i++){ for(int j=0;j<sz;j++){ m[i][j]=mid[i][j]; } } } }; matrix qpow(matrix x,ll p){ matrix ans; for(int i=0;i<sz;i++){ ans.m[i][i]=1; } while(p>0){ if(p&1) ans.mul(x); x.selfmul(); p>>=1; } return ans; } const int maxm=1e5+300; int T; int n,m; bool trans[60][60]; int main(){ freopen("/home/files/CppFiles/in","r",stdin); //freopen("/home/files/CppFiles/out","w",stdout); cin>>T; while(T--){ memset(trans,0,sizeof trans); scanf("%d%d",&n,&m); sz=n*2; for(int i=1;i<=n;i++){ int k; scanf("%d",&k); for(int j=0;j<k;j++){ int x; scanf("%d",&x); trans[i-1][x-1]=1; } } matrix tt; for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ tt.m[i][j]=trans[i][j]; } } for(int i=n;i<2*n;i++){ int j=i-n; tt.m[i][j]=1; tt.m[i][i]=1; } matrix ans=qpow(tt,m); int sum=0; for(int i=n;i<2*n;i++){ for(int j=0;j<n;j++) sum=(sum+ans.m[i][j])%mod; } printf("%d ",(sum+1)%mod); } return 0; }