cf621 E. Wet Shark and Blocks

题意：

长为 n 的数组，元素都是 \(1\sim 9\) 的整数。每次从数组中有放回地取数，取 b 次，把取出来的数组成一个大整数。问使得这个大整数 \(\%x=k\) 的方案数。

\(1\le a_i\le 9,2\le n\le 5e4, 1\le b\le 1e9,0\le k

思路：

\(dp(i,j)\) 表示取了 \(i\) 位数，凑出来的和模 x 为 \(j\) 的方案数。则 \(dp(i+1,(10j+a_{1\sim n})\%x)+=dp(i,j)\)

矩阵快速幂优化，行向量的第 \(j\) 个元素 \(B(j)\) 表示凑出 \(j\) 的方案数，\(0\le j < x\)

\[\begin{pmatrix} B_0 & B_1 & \cdots & B_{x-1} \end{pmatrix} \begin{pmatrix} \cdots & A_{0,j} & \cdots \\ \cdots & A_{1,j} & \cdots \\ & \vdots & \\ \cdots & A_{x-1,j} & \cdots \end{pmatrix} = \begin{pmatrix} \cdots & B'_{j} & \cdots \end{pmatrix} \]

怎么构造 \(A\) 呢？要让新的 \(B_j' = \sum\limits _{ (10i+v)\%x=j } B_i\)，只需对数组中的每个数 \(v\)，把 \(A[i][j=(10i+v)\%x]\) 加上1

注意到一开始 \(B=(1,0,0,\cdots)\)，所以答案是 \(A[0][k]\)

cin >> n >> b >> k >> x;
for(int i = 1; i <= n; i++) {
    ll v; cin >> v;
    for(int j = 0; j < x; j++)
        ++A[j][(j*10+v)%x];
}

qmi(A, b);
cout << A[0][k];