题意：

有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 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; }