hdu 5411 CRB and Puzzle 矩阵快速幂

题意：有n种数量无限的方块，每种方块后可以拼接另一个方块，但是只能拼接给定种类的方块，问最多拼接M次能拼接出多少种不同的样式。

这道题中n只有50，很容易想到矩阵快速幂，毕竟这种题已经烂大街了。然而比赛的时候我居然没有读到这道题！！！！！
重点在于构造转移矩阵，显然如果a后面可以拼接b，那么有$tmp[a][b]=1;$代表a->b有一种转移方式，构造完了之后，对这个矩阵自乘m次，那么矩阵的结果$tmp'[a][b]$代表的就是起点为a，终点为b，经过m次转移的方法数，但是我们要求0次转移 1次转移 2次转移 。。。M次转移的总和，所以把最后一列赋为1，就可以了。
第一次写的时候矩阵构造太挫T了，然后优化了一点勉强过了，
第二次和第三次都是优化过的。
优化过的矩阵构造。
代码1：

//author: CHC
//First Edit Time:	2015-08-25 21:13
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <algorithm>
#include <limits>
//#include <time.h>
using namespace std;
typedef long long LL;
const int INF = numeric_limits<int>::max();
const LL LL_INF= numeric_limits<LL>::max();
const int N = 53;
const int mod=2015;
int T,n,m,k,tn;
//C=A*B
void matric_mul(int A[][N],int B[][N],int C[][N]){
    int t[N][N]={0};
    for(int k=0;k<tn;k++){
        for(int i=0;i<tn;i++){
            if(A[i][k]==0)continue;
            for(int j=0;j<tn;j++){
                t[i][j]+=A[i][k]*B[k][j];
                t[i][j]%=mod;
            }
        }
    }
    for(int i=0;i<tn;i++){
        for(int j=0;j<tn;j++){
            C[i][j]=t[i][j];
        }
    }
}
int res[N][N],tmp[N][N];
void print(int A[][N]){
    for(int i=0;i<tn;i++,puts(""))
        for(int j=0;j<tn;j++)printf("%d ",A[i][j]);
    puts("");
}
int q_pow(int nn){
    //printf("res:\n");
    //print(res);
    while(nn>0){
        if(nn&1)matric_mul(res,tmp,res);
        //printf("res:\n");
        //print(res);
        nn>>=1;
        matric_mul(tmp,tmp,tmp);
    }
    int cnt=res[0][n];
    //for(int i=n;i<tn;i++)cnt+=res[0][i];
    return (cnt+1)%mod;
}
void Rd(int &x){
    char ch;
    while((ch=getchar())&&!isdigit(ch));
    x=0;
    do {
        x=(x<<3)+(x<<1)+(ch^48);
    }while((ch=getchar())&&isdigit(ch));
}
int main()
{
    //freopen("1006.in","r",stdin);
    //freopen("10061.out","w",stdout);
    //clock_t now=clock();
    int maxn=0,maxm=0;
    scanf("%d",&T);
    while(T--){
        //scanf("%d%d",&n,&m);
        Rd(n),Rd(m);
        maxn=max(n,maxn),maxm=max(m,maxm);
        tn=n+1;
        memset(tmp,0,sizeof(tmp));
        memset(res,0,sizeof(res));
        for(int i=0,x;i<n;i++){
            //scanf("%d",&k);
            Rd(k);
            for(int j=0;j<k;j++){
                //scanf("%d",&x);
                Rd(x);
                --x;
                tmp[i][x]=1;
                //tmp[i][x+n]=1;
            }
        }
        //for(int i=n;i<tn;i++)tmp[i][i]=1;
        for(int i=0;i<=n;i++)tmp[i][n]=1;
        //print(tmp);
        for(int i=0;i<n;i++)res[0][i]=1;
        res[0][n]=0;
        //print(res);
        printf("%d\n",q_pow(m));
    }
    //printf("%d %d\n",maxn,maxm);
    //printf("%.2lf\n",1.0*(clock()-now)/CLOCKS_PER_SEC);
    return 0;
}
/*
   10
   3 10
   1 2
   1 3
   0
   */

代码2:

//author: CHC
//First Edit Time:	2015-08-25 21:13
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <algorithm>
#include <limits>
//#include <time.h>
using namespace std;
typedef long long LL;
const int INF = numeric_limits<int>::max();
const LL LL_INF= numeric_limits<LL>::max();
const int N = 52;
const int mod=2015;
int T,n,m,k,tn;
//C=A*B
void matric_mul(int A[][N],int B[][N],int C[][N]){
    int t[N][N]={0};
    for(int k=0;k<tn;k++){
        for(int i=0;i<tn;i++){
            if(A[i][k]==0)continue;
            for(int j=0;j<tn;j++){
                t[i][j]+=A[i][k]*B[k][j];
                t[i][j]%=mod;
            }
        }
    }
    for(int i=0;i<tn;i++){
        for(int j=0;j<tn;j++){
            C[i][j]=t[i][j];
        }
    }
}
int res[N][N],tmp[N][N];
void print(int A[][N]){
    for(int i=0;i<tn;i++,puts(""))
        for(int j=0;j<tn;j++)printf("%d ",A[i][j]);
    puts("");
}
int q_pow(int nn){
    //printf("res:\n");
    //print(res);
    while(nn>0){
        if(nn&1)matric_mul(res,tmp,res);
        //printf("res:\n");
        //print(res);
        nn>>=1;
        matric_mul(tmp,tmp,tmp);
    }
    int cnt=0;
    for(int i=0;i<tn;i++)
        for(int j=0;j<tn;j++)cnt+=res[i][j];
    return (cnt)%mod;
}
void Rd(int &x){
    char ch;
    while((ch=getchar())&&!isdigit(ch));
    x=0;
    do {
        x=(x<<3)+(x<<1)+(ch^48);
    }while((ch=getchar())&&isdigit(ch));
}
int main()
{
    //freopen("1006.in","r",stdin);
    //freopen("10061.out","w",stdout);
    //clock_t now=clock();
    //int maxn=0,maxm=0;
    scanf("%d",&T);
    while(T--){
        //scanf("%d%d",&n,&m);
        Rd(n),Rd(m);
        //maxn=max(n,maxn),maxm=max(m,maxm);
        tn=n+1;
        memset(tmp,0,sizeof(tmp));
        memset(res,0,sizeof(res));
        for(int i=0;i<=n;i++)res[i][i]=1;
        for(int i=0,x;i<n;i++){
            //scanf("%d",&k);
            Rd(k);
            for(int j=0;j<k;j++){
                //scanf("%d",&x);
                Rd(x);
                --x;
                tmp[i][x]=1;
                //tmp[i][x+n]=1;
            }
        }
        for(int i=0;i<=n;i++)tmp[i][n]=1;
        //for(int i=n;i<tn;i++)tmp[i][i]=1;
        //print(tmp);
        //for(int i=0;i<tn;i++)res[0][i]=1;
        //print(res);
        printf("%d\n",q_pow(m-1));
    }
    //printf("%d %d\n",maxn,maxm);
    //printf("%.2lf\n",1.0*(clock()-now)/CLOCKS_PER_SEC);
    return 0;
}
/*
   10
   3 10
   1 2
   1 3
   0
   */

代码3:

//author: CHC
//First Edit Time:	2015-08-25 21:13
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <algorithm>
#include <limits>
//#include <time.h>
using namespace std;
typedef long long LL;
const int INF = numeric_limits<int>::max();
const LL LL_INF= numeric_limits<LL>::max();
const int N = 100;
const int mod=2015;
int T,n,m,k,tn;
//C=A*B
void matric_mul(int A[][N],int B[][N],int C[][N]){
    int t[N][N]={0};
    for(int k=0;k<tn;k++){
        for(int i=0;i<tn;i++){
            if(A[i][k]==0)continue;
            for(int j=0;j<tn;j++){
                t[i][j]+=A[i][k]*B[k][j];
                t[i][j]%=mod;
            }
        }
    }
    for(int i=0;i<tn;i++){
        for(int j=0;j<tn;j++){
            C[i][j]=t[i][j];
        }
    }
}
int res[N][N],tmp[N][N];
void print(int A[][N]){
    for(int i=0;i<tn;i++,puts(""))
        for(int j=0;j<tn;j++)printf("%d ",A[i][j]);
    puts("");
}
int q_pow(int nn){
    //printf("res:\n");
    //print(res);
    while(nn>0){
        if(nn&1)matric_mul(res,tmp,res);
        //printf("res:\n");
        //print(res);
        nn>>=1;
        matric_mul(tmp,tmp,tmp);
    }
    int cnt=0;
    for(int i=n;i<tn;i++)cnt+=res[0][i];
    return (cnt+1)%mod;
}
void Rd(int &x){
    char ch;
    while((ch=getchar())&&!isdigit(ch));
    x=0;
    do {
        x=(x<<3)+(x<<1)+(ch^48);
    }while((ch=getchar())&&isdigit(ch));
}
int main()
{
    //freopen("1006.in","r",stdin);
    //freopen("10061.out","w",stdout);
    //clock_t now=clock();
    int maxn=0,maxm=0;
    scanf("%d",&T);
    while(T--){
        //scanf("%d%d",&n,&m);
        Rd(n),Rd(m);
        maxn=max(n,maxn),maxm=max(m,maxm);
        tn=2*n;
        memset(tmp,0,sizeof(tmp));
        memset(res,0,sizeof(res));
        for(int i=0,x;i<n;i++){
            //scanf("%d",&k);
            Rd(k);
            for(int j=0;j<k;j++){
                //scanf("%d",&x);
                Rd(x);
                --x;
                tmp[i][x]=1;
                tmp[i][x+n]=1;
            }
        }
        for(int i=n;i<tn;i++)tmp[i][i]=1;
        //print(tmp);
        for(int i=0;i<tn;i++)res[0][i]=1;
        //print(res);
        printf("%d\n",q_pow(m-1));
    }
    //printf("%d %d\n",maxn,maxm);
    //printf("%.2lf\n",1.0*(clock()-now)/CLOCKS_PER_SEC);
    return 0;
}
/*
   10
   3 10
   1 2
   1 3
   0
   */