传送门：点击打开链接
题意：一个块中有n个数字，一共有b个块，每个块里的n个数字一模一样，现在在每个块中选一个数字，然后首尾串成一个大整数，把这个整数取模x，问有多少种情况最后的结果恰好等于k
思路：如果不考虑b的大小，我们能想到数位dp，dp[k][(i*10+j)%x]+=dp[k-1][i]*num[j] (1<=j<=9)，dp[k][i]表示现在正在考虑前k个块，此时结果取模x等于i的方案数。
但是我们发现，b实在是太大了，但是线性递推都是能用快速矩阵幂来搞的，这个也不例外，我们直接根据方程构造出矩阵，然后用快速矩阵幂就能得到答案了。
#include<map>
#include<set>
#include<cmath>
#include<ctime>
#include<stack>
#include<queue>
#include<cstdio>
#include<cctype>
#include<string>
#include<vector>
#include<cstring>
#include<iomanip>
#include<iostream>
#include<algorithm>
#include<functional>
#define fuck(x) cout<<"["<<x<<"]"
#define FIN freopen("input.txt","r",stdin)
#define FOUT freopen("output.txt","w+",stdout)
using namespace std;
typedef long long LL;
typedef pair<LL, int>PII;const int MX = 2e3 + 10;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;typedef vector<int> vec;
typedef vector<vec> mat;
mat mat_mul(mat &A, mat &B) {mat C(A.size(), vec(B[0].size()));for(int i = 0; i < A.size(); i++) {for(int j = 0; j < B[0].size(); j++) {for(int k = 0; k < B.size(); k++) {C[i][j] = ((LL)A[i][k] * B[k][j] + C[i][j]) % mod;}}}return C;
}
mat mat_pow(mat A, LL n) {mat B(A.size(), vec(A.size()));for(int i = 0; i < A.size(); i++) B[i][i] = 1;while(n) {if(n & 1) B = mat_mul(B, A);A = mat_mul(A, A);n >>= 1;}return B;
}int cnt[10];
int main() {int n, b, k, x; //FIN;scanf("%d%d%d%d", &n, &b, &k, &x);for(int i = 1; i <= n; i++) {int t; scanf("%d", &t);cnt[t]++;}mat A(x, vec(x)), B(x, vec(1)); B[0][0] = 1;for(int i = 0; i < x; i++) {for(int j = 1; j <= 9; j++) {A[(i * 10 + j) % x][i] += cnt[j];}}A = mat_pow(A, b);B = mat_mul(A, B);printf("%d\n", B[k][0]);return 0;
}