题意：

有b个blocks，每个blocks都有n个相同的0~9的数字，如果从第一个block选1，从第二个block选2，那么就构成12，问对于给定的n,b有多少种构成方案使最后模x的余数为k。

分析：

dp+矩阵快速幂。

假如现在的数是m，模x余数是n，那么再从下一个block中选一个数a，a模x余数为b，那么新的数的余数就为(m∗10+a)%x，也就是(n∗10+b)%x，所以实际上我们只需要直接对余数进行操作。容易得到状态转移方程，其中dp[i][j]表示从第i个block中选择一个数后，余数为j的方案数，cnt[m]为余数为m的数的个数。

dp[i][(j * 10 + m) % x] = dp[i-1][j] * cnt[m];

可是b高达109，规模太大直接递推的话效率太低，而x最大仅为100，直接用矩阵表示这个递推式，时间复杂度则降为O(x3logb)。

代码：

#include<cstdio>

const int maxn = 50005;

int cnt[maxn], r[maxn];

const int N = 105, mod = 1e9 + 7;

struct Matrix

{

    int row,cal;

    long long  m[N][N];

};

Matrix init(Matrix a, long long t)

{

    for(int i = 0; i < a.row; i++)

        for(int j = 0; j < a.cal; j++)

            a.m[i][j] = t;

    return a;

}

Matrix mul(Matrix a,Matrix b)

{

    Matrix ans;

    ans.row = a.row, ans.cal = b.cal;

    ans = init(ans,0);

    for(int i = 0; i < a.row; i++)

        for(int j = 0; j < b.cal; j++)

            for(int k = 0; k < a.cal; k++)

                ans.m[i][j] = (ans.m[i][j] + a.m[i][k] * b.m[k][j])%mod;

    return ans;

}

long long quick_pow(int k, int x, int res, Matrix A)

{

    Matrix I;

    I.row = x, I.cal = 1;

    I = init(I, 0);

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

            I.m[i][0] = cnt[i];

    while(k){

        if(k&1) I = mul(A, I);

        A = mul(A, A);

        k>>=1;

    }

    return I.m[res][0]%mod;

}

int main (void)

{

    int n, b, k, x;

    int a;

    scanf("%d%d%d%d",&n,&b,&k,&x);

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

        scanf("%d",&a);

        cnt[a%x]++;

    }

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

        r[i] = (i *10)%x;

    Matrix t;

    t.row = t.cal = x;

    for(int i = 0; i < t.row; i++)

        for(int j = 0; j < t.cal; j++)

            t.m[i][j] = cnt[(i+x-r[j])%x];

    printf("%I64d",quick_pow(b-1, x, k, t));

    return 0;

}