目标
给你一个由 正 整数组成的数组 nums，以及一个 正 整数 k。
你可以对 nums 执行 一次 操作，该操作中可以移除任意 不重叠 的前缀和后缀，使得 nums 仍然 非空 。
你需要找出 nums 的 x 值，即在执行操作后，剩余元素的 乘积 除以 k 后的 余数 为 x 的操作数量。
返回一个大小为 k 的数组 result，其中 result[x] 表示对于 0 <= x <= k - 1，nums 的 x 值。
数组的 前缀 指从数组起始位置开始到数组中任意位置的一段连续子数组。
数组的 后缀 是指从数组中任意位置开始到数组末尾的一段连续子数组。
子数组 是数组中一段连续的元素序列。
注意，在操作中选择的前缀和后缀可以是 空的 。
示例 1：
输入： nums = [1,2,3,4,5], k = 3
输出： [9,2,4]
解释：
对于 x = 0，可行的操作包括所有不会移除 nums[2] == 3 的前后缀移除方式。
对于 x = 1，可行操作包括：
移除空前缀和后缀 [2, 3, 4, 5]，nums 变为 [1]。
移除前缀 [1, 2, 3] 和后缀 [5]，nums 变为 [4]。
对于 x = 2，可行操作包括：
移除空前缀和后缀 [3, 4, 5]，nums 变为 [1, 2]。
移除前缀 [1] 和后缀 [3, 4, 5]，nums 变为 [2]。
移除前缀 [1, 2, 3] 和空后缀，nums 变为 [4, 5]。
移除前缀 [1, 2, 3, 4] 和空后缀，nums 变为 [5]。示例 2：
输入： nums = [1,2,4,8,16,32], k = 4
输出： [18,1,2,0]
解释：
对于 x = 0，唯一 不 得到 x = 0 的操作有：
移除空前缀和后缀 [4, 8, 16, 32]，nums 变为 [1, 2]。
移除空前缀和后缀 [2, 4, 8, 16, 32]，nums 变为 [1]。
移除前缀 [1] 和后缀 [4, 8, 16, 32]，nums 变为 [2]。
对于 x = 1，唯一的操作是：
移除空前缀和后缀 [2, 4, 8, 16, 32]，nums 变为 [1]。
对于 x = 2，可行操作包括：
移除空前缀和后缀 [4, 8, 16, 32]，nums 变为 [1, 2]。
移除前缀 [1] 和后缀 [4, 8, 16, 32]，nums 变为 [2]。
对于 x = 3，没有可行的操作。示例 3：
输入： nums = [1,1,2,1,1], k = 2
输出： [9,6]说明：
- 1 <= nums[i] <= 10^9
- 1 <= nums.length <= 10^5
- 1 <= k <= 5
思路
有一个正整数数组 nums 和一个正整数 k，每次操作可以移除数组不重叠的前缀与后缀，即保留中间非空的子数组。求子数组元素乘积模 k 的余数为 x 的操作数量。
定义 dp[i][j] 表示 [0, i] 中以 i 为右端点的子数组中模 k 余 j 的个数。使用刷表法更新 dp[i][nums[i] % k]++, dp[i][nums[i] * j % k] += dp[i - 1][j]。
代码
/**
* @date 2026-09-21 15:19
*/
public class ResultArray3524 {
public long[] resultArray(int[] nums, int k) {
int n = nums.length;
long[][] dp = new long[n][k];
dp[0][nums[0] % k] = 1;
long[] res = new long[k];
res[nums[0] % k]++;
for (int i = 1; i < n; i++) {
int rem = nums[i] % k;
dp[i][rem]++;
for (int j = 0; j < k; j++) {
dp[i][(int) ((long) nums[i] * j % k)] += dp[i - 1][j];
}
for (int j = 0; j < k; j++) {
res[j] += dp[i][j];
}
}
return res;
}
}
性能
