codeforces #341 div 2 E. Wet Shark and Blocks (数位dp+矩阵加速)

  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}