http://codeforces.com/problemset/problem/621/E#
题意：有b组数，每组数均有n个且相同。你必须在每组选一个数，组成一个新数sum，使得sum % x == k，问方案数 % (1e9+7)。
思路：数位dp.首先考虑b不是很大的一般情况。dp[i][j]表示处理到前i个块的时候结果为j的方案数。那么转移方程就是：**dp[i][(j_10+t)%x] = dp[i-1][j]_cnt[t] ** cnt[i]表示数字i出现的个数。
但是由于b很大（1E9）,所以需要用矩阵加速。
1/* ***********************************************
2Author :111qqz
3Created Time :2016年02月08日 星期一 16时24分34秒
4File Name :code/cf/#341/E.cpp
5************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define fst first
20#define sec second
21#define lson l,m,rt<<1
22#define rson m+1,r,rt<<1|1
23#define ms(a,x) memset(a,x,sizeof(a))
24typedef long long LL;
25#define pi pair < int ,int >
26#define MP make_pair
27
28using namespace std;
29const double eps = 1E-8;
30const int dx4[4]={1,0,0,-1};
31const int dy4[4]={0,-1,1,0};
32const int inf = 0x3f3f3f3f;
33const LL MOD=1E9+7;
34int n,b,k,X;
35struct Matrix
36{
37 LL a[110][110];
38
39};
40
41void add(LL &x,LL y)
42{
43 x += y;
44 x %= MOD;
45}
46Matrix multi(Matrix x,Matrix y ) //矩阵乘法。
47{
48 Matrix z;
49 ms(z.a,0LL);
50 for ( int i = 0 ; i < X ;i++)
51 {
52 for ( int k = 0 ; k < X ; k++)
53 {
54 if (x.a[i][k]==0) continue;
55 for ( int j = 0 ; j < X ; j++)
56 add(z.a[i][j],x.a[i][k]*y.a[k][j]);
57
58 }
59 }
60 return z;
61}
62
63Matrix Pow(Matrix x,int n) //矩阵快速幂
64{
65 Matrix y;
66 ms(y.a,0LL);
67 for ( int i = 0 ; i < X ; i++) y.a[i][i] = 1LL;
68 while (n)
69 {
70 if (n&1)
71 y = multi(x,y);
72 x = multi(x,x);
73 n >>=1;
74 }
75 return y;
76}
77
78int cnt[20];
79int main()
80{
81 #ifndef ONLINE_JUDGE
82 freopen("code/in.txt","r",stdin);
83 #endif
84
85 cin>>n>>b>>k>>X;
86
87 Matrix ori,res;
88 ms(ori.a,0LL);
89 ms(cnt,0);
90 for ( int i = 1 ; i <= n ; i++)
91 {
92 int tmp;
93 scanf("%d",&tmp);
94 cnt[tmp]++;
95 }
96
97 for ( int i = 0 ; i < X ; i++)
98 for (int j = 0 ; j <= 9 ; j++)
99 add(ori.a[i][(i*10+j)%X],1LL*cnt[j]);
100 res = Pow(ori,b);
101 cout<<res.a[0][k]<<endl;
102
103
104 #ifndef ONLINE_JUDGE
105 fclose(stdin);
106 #endif
107 return 0;
108}