# CFR 621 E. Wet Shark and Blocks ( DP, Fast Matrix Multiplication )

Problem - E - Codeforces

1  ≤ B  ≤  1e9,  0 ≤ K  <  X  ≤  100, x  ≥  2

dp[ i ][ j ][ k ] : 挑 i 個數字後，原本為 j，變成 k 的方法數
dp[ i ][ j ][ k ] = SIGMA{ dp[ i - 1 ][ j ][ m ] * dp[ i - 1 ][ m ][ k ] | for each j ≤ M ≤ k }

O( N + X ^ 3 lg B )

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;
const int MAXN = 5e4 + 5;
const int MAXB = 1e9;
const int MAXX = 100;
const int MOD = 1e9 + 7;

mat mul(const mat &a, const mat &b){
mat c( a.size(), vec( b[0].size() ) );
for(int i = 0; i < a.size(); ++i)
for(int k = 0; k < b.size(); ++k)
for(int j = 0; j < b[0].size(); ++j)
c[i][j] = ( c[i][j] + a[i][k] * b[k][j] ) % MOD;
return c;
}

mat pw(mat a, ll b){
mat c( a.size(), vec( a[0].size() ) );
for(int i = 0; i < a.size(); ++i) c[i][i] = 1;
while( b > 0 ){
if( b & 1LL ) c = mul( c, a );
a = mul( a, a );
b >>= 1LL;
}
return c;
}

int arr[MAXN];
int main(){
ios::sync_with_stdio(false);
int n, b, k, x;
cin >> n >> b >> k >> x;
for(int i = 0; i < n; ++i)
cin >> arr[i];
mat a( x, vec( x ) );
for(int i = 0; i < x; ++i)
for(int j = 0; j < n; ++j)
++a[i][ ( 10 * i + arr[j] ) % x ];
a = pw( a, b );
cout << a[0][k] << endl;
return 0;
}