Solution

首先观察到题目，可以迅速得出一个很板的dp。
$$
f[i+1][(j*10+v[l])\% x]+=f[i][j]
$$
其中$f[i][j]$表示前$i$个格子余数是$j$的方案数。

可以发现每一次枚举$l$的操作纯属多余（每次都一样），考虑到数据点的范围分布极不合理的现象，显然正解应该是矩阵快速幂。

考虑构造矩阵，定义矩阵$A$表示：前一个格子构造的余数为$i$这一个格子将余数变成$j$的方案数。

这样的矩阵显然是相关的，所以可以用矩阵快速幂。

具体的每读进来一个数，所有的$A[j][(j*10+v)%x]$都必须$+1$。

最后的$A[0]][k]$就是答案。

Code

#include<bits/stdc++.h>
#define PII pair<int, LL>
#define LL long long
using namespace std;
template <class T>
inline void read(T &res)
{
	res = 0; bool flag = 0;
	char c = getchar();
	while(c < '0' || '9' < c) {if(c == '-') flag = 1; c = getchar();}
	while('0' <= c && c <= '9') res = (res << 3) + (res << 1) + (c ^ 48), c = getchar();
	if(flag) res = -res; 
}
template <class T, class ...ARC>
inline void read(T &res, ARC &...com){ read(res), read(com...); }
template <class T>
void write(T res)
{
	if(res < 0) putchar('-'), res = -res;
	if(res > 9) write(res / 10);
	putchar(res % 10 + '0');
}
template <>
inline void write(char c) { putchar(c); }
template <>
inline void write(char *s) { while(*s) putchar(*s ++);}
template <class T, class ...ARC>
inline void write(T res, ARC ...com) { write(res), write(com...); } 
const int N = 105, mod = 1e9 + 7;
int n, b, k, x;
struct Node{
    int a[N][N];
    Node operator* (Node b)
    {
        Node c;
        memset(c.a, 0, sizeof(c.a));
        for(int i = 0;i < x;i ++)
            for(int j = 0;j < x;j ++)
                for(int k = 0;k < x;k ++)
                    c.a[i][j] = (c.a[i][j] + 1ll * a[i][k] * b.a[k][j] % mod) % mod;
        return c;
    }
}a;
inline Node qpow(Node x, int k)
{
    Node res = x;
    k --;
    while(k)
    {
        if(k & 1) res = res * x;
        k >>= 1;
        x = x * x;
    }
    return res;
}
int main()
{
    read(n, b, k, x);
    for(int i = 1, v;i <= n;i ++)
    {
        read(v);
        for(int j = 0;j < x;j ++)
            a.a[j][(j * 10 + v) % x] ++;
    }
    a = qpow(a, b);
    write(a.a[0][k]);
    return 0;
}

Luckyleaves's Blog

CF621E Wet Shark and Blocks

Solution

Code