[cf621E]Wet Shark and Blocks

Description

给定\(n\)个数和\(b\)个盒子，放一些数到盒子中，使得盒子不为空。每个盒子中的数是一样的，一个数可以被放到多个盒子中。

从每个盒子中取一个数，组成一个\(b\)位数，如果这个数\(mod\;k=x\)，则这是一种合法的方案。求方案数\(mod\;10^9+7\)。

Input

第一行为\(4\)个数\(n,b,x,k\)。
第二行为\(n\)个数。

Output

一行，表示方案数\(mod 10^9+7\)。

Sample Input

3 2 1 2
3 1 2

Sample Output

6

HINT

\(2\;\leq\;n\;\leq\;50000,1\;\leq\;b\;\leq\;10^9,0\;\leq\;k\;\leq\;100, x\;\geq\;2,1\;\leq\;a_i\;\leq\;9\)

Solution

显然序列中有用的条件仅有每个数出现的次数，记为\(t[\;]\)。

\(f[i][j]\)表示前\(i\)位数\(mod\;k\)的值为\(j\)的方案数。

\(f[i+1][(j\;\times\;10+l)mod\;n]=f[i][j]\;\times\;t[l]\)。

矩乘优化\(DP\)就能过了。

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define lld I64d
#define K 15
#define N 105
#define M 1000000007
using namespace std;
typedef long long ll;
struct matrix{
    ll a[N][N];int n,m;
}a,b;
ll t[K];
int n,m,k,x;
inline matrix mult(matrix a,matrix b){
    matrix c;c.n=a.n;c.m=b.m;
    for(int i=0;i>=1;
    }
    return c;
}
inline void init(){
    scanf("%d%d%d%d",&n,&m,&x,&k);
    for(int i=1,j;i<=n;++i){
        scanf("%d",&j);++t[j];
    }
    a.n=k;a.m=1;
    for(int i=1;i<=9;++i)
        a.a[i%k][0]+=t[i];
    b.n=b.m=k;
    for(int i=0,l;i