题解 | #经典 DP#

题目链接

该问题似乎是特定竞赛的题目，暂无公开链接

题目描述

给定一个初始值 $c$ 和一个由 $n$ 个正整数组成的数组 $a=\{a_1, a_2, \dots, a_n\}$ 。定义一次操作如下：

选择数组 $a$ 中的若干个元素（至少一个），记元素之和为 $s$ 。
将 $c$ 更新为 $c \cdot s$ 。

求解有多少种不同的操作方案，使得恰好经过 $t$ 次操作后 $c \pmod m = k$ 。由于答案可能很大，请将答案对 $(10^9 + 7)$ 取模后输出。

记第 $i$ 次选取元素的下标构成的集合为 $S_i$ ，两个方案被视为不同的，当且仅当存在 $i$ 使得两个方案第 $i$ 次选取元素的下标构成的集合不同。

解题思路

这是一个多阶段决策的计数问题。由于操作次数 $t$ 非常大，而状态空间（模 $m$ 的余数）相对较小，这强烈地暗示了需要使用矩阵快速幂来进行优化。

动态规划模型

首先，我们可以建立一个基础的动态规划模型。令 $dp[i][j]$ 表示经过 $i$ 次操作后，当前值为 $j$ 的方案数。我们的目标是求 $dp[t][k]$ 。

初始状态: 0 次操作后，只有初始状态 $c \pmod m$ 是可达的。因此， $dp[0][c \pmod m] = 1$ ，对于所有其他的 $j \neq c \pmod m$ ，有 $dp[0][j] = 0$ 。
状态转移: 考虑从第 $i-1$ 步转移到第 $i$ 步。假设第 $i-1$ 步后值为 $l$ ，在第 $i$ 步操作中，我们选择了一个和为 $s$ 的非空子集，使得新状态的值为 $j = (l \cdot s) \pmod m$ 。

为了进行转移，我们首先需要预计算出单次操作所有可能的乘数 $s$ （模 $m$ 意义下）及其对应的方案数。令 $count[v]$ 为从数组 $A$ 中选取一个非空子集，使其元素和模 $m$ 为 $v$ 的方案数。

那么， $dp[i][j]$ 可以由所有 $dp[i-1][l]$ 的状态转移过来。一个状态 $l$ 能转移到 $j$ ，当且仅当存在一个乘数 $v$ 使得 $(l \cdot v) \pmod m = j$ 。
$dp[i][j] = \sum_{l=0}^{m-1} \sum_{v \text{ s.t. } (l \cdot v) \pmod m = j} dp[i-1][l] \cdot count[v]$

矩阵快速幂优化

上述 DP 转移过程可以用矩阵乘法来描述。设 $D_i$ 是一个 $m \times 1$ 的列向量，其中 $D_i[j] = dp[i][j]$ 。我们可以构建一个 $m \times m$ 的转移矩阵 $T$ ，使得 $D_i = T \cdot D_{i-1}$ 。

根据状态转移方程，矩阵 $T$ 的第 $j$ 行第 $l$ 列的元素 $T_{j,l}$ 表示从状态 $l$ 转移到状态 $j$ 的总方案数。这个方案数等于所有能使 $(l \cdot v) \pmod m = j$ 成立的 $v$ 对应的 $count[v]$ 之和。

T_{j,l} = \sum_{v \text{ s.t. } (l \cdot v) \pmod m = j} count[v]

在得到转移关系 $D_i = T \cdot D_{i-1}$ 后，我们可以推导出 $D_t = T^t \cdot D_0$ 。我们可以使用矩阵快速幂在 $O(m^3 \log t)$ 的时间内计算出 $T^t$ 。

算法步骤

计算 count 数组: 使用 $O(n \cdot m)$ 的动态规划（类似于 0-1 背包）计算出从数组 $A$ 中任取子集（可为空）得到各个余数 $v \in [0, m-1]$ 的方案数 ways[v]。然后，count[v] = ways[v]，但 count[0] 需要减 1 以排除空集的情况。
构建转移矩阵 T: 创建一个 $m \times m$ 的零矩阵。遍历所有旧状态 $l \in [0, m-1]$ 和所有可能的乘数余数 $v \in [0, m-1]$ ，计算出新状态 $j = (l \cdot v) \pmod m$ ，然后将 $count[v]$ 的值累加到 $T_{j,l}$ 上。这一步的复杂度是 $O(m^2)$ 。
矩阵快速幂: 使用矩阵乘法和快速幂算法计算出最终的转移矩阵 $T_{final} = T^t$ 。
求解: 最终的答案是 $D_t[k]$ 。由于 $D_0$ 是一个单位向量（只有一个位置是 1，其余是 0）， $D_0[c \pmod m]=1$ ，所以 $D_t[k] = \sum_{l=0}^{m-1} (T^t)_{k,l} \cdot D_0[l] = (T^t)_{k, c \pmod m}$ 。答案就是最终矩阵 $T_{final}$ 的第 $k$ 行，第 $c \pmod m$ 列的元素。

代码

c++
java
python

#include <iostream>
#include <vector>
#include <numeric>

using namespace std;

const int MOD = 1e9 + 7;

using Matrix = vector<vector<long long>>;

Matrix multiply(const Matrix& a, const Matrix& b, int m) {
    Matrix c(m, vector<long long>(m, 0));
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < m; ++j) {
            for (int l = 0; l < m; ++l) {
                c[i][j] = (c[i][j] + a[i][l] * b[l][j]) % MOD;
            }
        }
    }
    return c;
}

Matrix matrix_pow(Matrix base, int exp, int m) {
    Matrix res(m, vector<long long>(m, 0));
    for (int i = 0; i < m; ++i) res[i][i] = 1;
    while (exp > 0) {
        if (exp % 2 == 1) res = multiply(res, base, m);
        base = multiply(base, base, m);
        exp /= 2;
    }
    return res;
}

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    long long c_init;
    int m, k, t;
    for (int i = 0; i < n; ++i) cin >> a[i];
    cin >> c_init >> m >> k >> t;

    vector<long long> ways(m, 0);
    ways[0] = 1;
    for (int val : a) {
        vector<long long> next_ways = ways;
        int rem = val % m;
        for (int i = 0; i < m; ++i) {
            next_ways[i] = (next_ways[i] + ways[(i - rem + m) % m]) % MOD;
        }
        ways = next_ways;
    }
    
    vector<long long> count = ways;
    count[0] = (count[0] - 1 + MOD) % MOD;

    Matrix T(m, vector<long long>(m, 0));
    for (int l = 0; l < m; ++l) {
        for (int v = 0; v < m; ++v) {
            if (count[v] > 0) {
                int j = (1LL * l * v) % m;
                T[j][l] = (T[j][l] + count[v]) % MOD;
            }
        }
    }
    
    Matrix T_final = matrix_pow(T, t, m);
    
    int c_start_mod = c_init % m;
    
    cout << T_final[k][c_start_mod] << endl;

    return 0;
}

import java.util.Scanner;

public class Main {
    private static final int MOD = 1_000_000_007;

    private static long[][] multiply(long[][] a, long[][] b, int m) {
        long[][] c = new long[m][m];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < m; j++) {
                for (int l = 0; l < m; l++) {
                    c[i][j] = (c[i][j] + a[i][l] * b[l][j]) % MOD;
                }
            }
        }
        return c;
    }

    private static long[][] matrixPow(long[][] base, int exp, int m) {
        long[][] res = new long[m][m];
        for (int i = 0; i < m; i++) {
            res[i][i] = 1;
        }
        while (exp > 0) {
            if (exp % 2 == 1) {
                res = multiply(res, base, m);
            }
            base = multiply(base, base, m);
            exp /= 2;
        }
        return res;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        long c_init = sc.nextLong();
        int m = sc.nextInt();
        int k = sc.nextInt();
        int t = sc.nextInt();

        long[] ways = new long[m];
        ways[0] = 1;
        for (int val : a) {
            long[] next_ways = new long[m];
            System.arraycopy(ways, 0, next_ways, 0, m);
            int rem = val % m;
            for (int i = 0; i < m; i++) {
                next_ways[i] = (next_ways[i] + ways[(i - rem + m) % m]) % MOD;
            }
            ways = next_ways;
        }
        
        long[] count = ways;
        count[0] = (count[0] - 1 + MOD) % MOD;
        
        long[][] T = new long[m][m];
        for (int l = 0; l < m; l++) {
            for (int v = 0; v < m; v++) {
                if (count[v] > 0) {
                    int j = (int) ((1L * l * v) % m);
                    T[j][l] = (T[j][l] + count[v]) % MOD;
                }
            }
        }
        
        long[][] T_final = matrixPow(T, t, m);
        
        int c_start_mod = (int) (c_init % m);
        
        System.out.println(T_final[k][c_start_mod]);
    }
}

MOD = 10**9 + 7

def multiply(a, b, m):
    c = [[0] * m for _ in range(m)]
    for i in range(m):
        for j in range(m):
            for l_ in range(m):
                c[i][j] = (c[i][j] + a[i][l_] * b[l_][j]) % MOD
    return c

def matrix_pow(base, exp, m):
    res = [[0] * m for _ in range(m)]
    for i in range(m):
        res[i][i] = 1
    
    while exp > 0:
        if exp % 2 == 1:
            res = multiply(res, base, m)
        base = multiply(base, base, m)
        exp //= 2
    return res

def solve():
    n = int(input())
    a = list(map(int, input().split()))
    c_init, m, k, t = map(int, input().split())

    ways = [0] * m
    ways[0] = 1
    for val in a:
        next_ways = list(ways)
        rem = val % m
        for i in range(m):
            next_ways[i] = (next_ways[i] + ways[(i - rem + m) % m]) % MOD
        ways = next_ways
    
    count = ways
    count[0] = (count[0] - 1 + MOD) % MOD
    
    T = [[0] * m for _ in range(m)]
    for l in range(m):
        for v in range(m):
            if count[v] > 0:
                j = (l * v) % m
                T[j][l] = (T[j][l] + count[v]) % MOD
    
    T_final = matrix_pow(T, t, m)
    
    c_start_mod = c_init % m
    
    print(T_final[k][c_start_mod])

solve()

算法及复杂度

算法：动态规划 (子集和) + 矩阵快速幂
时间复杂度： $O(n \cdot m + m^3 \log t)$ - $O(n \cdot m)$ 来自于预计算子集和方案数， $O(m^3 \log t)$ 来自于矩阵快速幂。
空间复杂度： $O(m^2)$ - 主要用于存储转移矩阵。