The Goddess Of The Moon

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <algorithm>

using namespace std;

const int maxn = 55;

const int mod = 1e9+7;

int n, m, a[maxn];

struct Mat

{

    int s[maxn][maxn];

    Mat ()

    {

        memset(s, 0, sizeof(s));

    }

    Mat operator * (const Mat& b)

    {

        Mat ret;

        for (int k = 0; k < n; k++)

        {

            for (int i = 0; i < n; i++)

            {

                for (int j = 0; j < n; j++)

                    ret.s[i][j] = (ret.s[i][j] + 1LL * s[i][k] * b.s[k][j] % mod) % mod;

            }

        }

        return ret;

    }

};

bool work(int a,int b)

{

    char p[15], q[15];

    sprintf(p, "%d", a);

    sprintf(q, "%d", b);

    int l1 = strlen(p);

    int l2 = strlen(q);

    for(int i = 0; i < l1; i++)

    {

        int k = 0;

        while(i + k < l1 && k < l2 && p[i+k] == q[k])

        {

            k++;

        }

        if(i + k == l1 && k > 1)

            return true;

    }

    return false;

}

Mat solve()

{

    Mat lp;

    for(int i = 0; i < n; i++)

        for(int j = 0; j < n; j++)

        {

            if(work(a[i],a[j]))

                lp.s[i][j] = 1;

        }

    return lp;

}

Mat pow_mat(Mat x, int z)

{

    Mat ret;

    for (int i = 0; i < n; i++)

        ret.s[i][i] = 1;

    while (z)

    {

        if (z&1)

            ret = ret * x;

        x = x * x;

        z >>= 1;

    }

    return ret;

}

int main()

{

    int T;

    scanf("%d",&T);

    while(T--)

    {

        scanf("%d%d",&n,&m);

        for(int i = 0; i <n; i++)

            scanf("%d",&a[i]);

        sort(a,a+n);

        n = unique(a,a+n) - a;

        if (n == 0 || m == 0)

        {

            printf("0\n");

            continue;

        }

        Mat tp = solve();

        Mat tmp = pow_mat(tp,m-1);

        long long ans = 0;

        for(int i = 0; i < n; i++)

            for(int j = 0; j < n; j++)

                ans = (long long)(ans + tmp.s[i][j])%mod;

        printf("%I64d\n",ans);

    }

}

主要部分：

struct Matrix {

    LL m[55][55];

};

Matrix init;  

Matrix MatrixMul(Matrix a, Matrix b){

    Matrix c;

    int i,j,k;

    for(i=0;i<N;i++){

        for(j=0;j<N;j++){

            c.m[i][j]=0;

            for(k=0;k<N;k++){

                c.m[i][j]+=(a.m[i][k]*b.m[k][j]);

                c.m[i][j]%=kmod;

            }

        }

    }

    return c;

}  

Matrix QuickPow(Matrix m,int p){

    Matrix b;

    int i;

    memset(b.m,0,sizeof b.m);

    for(i=0;i<N;i++)

        b.m[i][i]=1;

    while(p){

        if(p%2) b=MatrixMul(b,m);

        p/=2;

        m=MatrixMul(m,m);

    }

    return b;

}