Wet Shark and Blocks

Created by LXC on Thu Jun 29 00:11:28 2023

https://codeforces.com/problemset/problem/621/E

ranting: 2000

tag: dp, matrices

problem

有n个数字，每个数字的取值在1到9。

每次可以从n个数字中选出一个数（选完后的数字还可以选），选取b次后，将这b个数拼接到一起，形成一个b位十进制数num。

问有多少种选法使得选出的num满足$num \equiv k \pmod{x}$

$2 ≤ n ≤ 50 000, 1 ≤ b ≤ 109, 0 ≤ k < x ≤ 100, x ≥ 2$

solution

我们统计1到9每个数字出现的个数，记$cnt_i$为i出现的次数。

容易想出状态跟当前第几次选以及所拼接形成的数（模x下）有关。

所以可以定义状态$f_{i,j}$为第i次选取，形成数为j的合法个数。

可以想到状态转移为$f_{i,(10j+c)\bmod x} = f_{i-1, j}\times cnt_c$

但是我们要的答案是$f_{b,k}$。b的取值高达$10^9$

考虑矩阵快速幂加速dp转移。
构造矩阵$B_{x\times x}$，$B_{i,j}$代表从当前状态$f_{p,i}$到下一状态$f_{p+1, j}$的部分贡献。

在这里我们让$cnt_c$分别累加到$B_{i,(10j+c)\bmod x}$

然后构造矩阵$A_{1\times x}$，$A_{0,i}$代表拼接成i的种数，初始$A_{0,0} = 1$，其余为0。

$A\times B^b$意味着$A_{0,i}$是在选取b次数字后拼接成i的种数。答案就是$A_{0,k}$

code

#include <bits/stdc++.h>
#define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define MOD 1000000007
using namespace std;

#define N 105

struct Matrix {
    int mat[N][N];
    int n;
    Matrix(int n) : n(n) { memset(mat, 0, sizeof(mat)); }
    inline void operator*=(const Matrix& o) {
        int ans[n][n] = {};
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if (mat[i][j])
                    for (int k = 0; k < n; k++)
                        ans[i][k] =
                            (ans[i][k] + (long long)(mat[i][j]) * o.mat[j][k]) %
                            MOD;
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                mat[i][j] = ans[i][j];
    }
    void print() {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                cout << mat[i][j] << " ";
            }
            cout << "\n";
        }
    }
};
/*
    // a *= b^n
    for (; n; n >>= 1, b *= b)
        if (n & 1)
            a *= b;
    a.print();
*/

void sol() {
    int n, b, k, x;
    cin >> n >> b >> k >> x;
    vector<int> cnt(10);
    for (int i = 0; i < n; i++) {
        int t;
        cin >> t;
        cnt[t]++;
    }
    Matrix A(x), B(x);
    for (int i = 0; i < x; i++) {
        for (int j = 1; j < 10; j++) {
            B.mat[i][(i * 10 + j) % x] += cnt[j];
        }
    }
    A.mat[0][0] = 1;
    for (; b; b >>= 1, B *= B) {
        if (b & 1)
            A *= B;
    }
    cout << A.mat[0][k] << "\n";
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}