5 3 125 1 8 1 1这个样例答案是错的
时间: 2023-12-29 11:05:38 浏览: 29
非常感谢您的指正,我之前的代码确实有问题,没有考虑到前缀积末尾为 0 的情况。
正确的做法是,在计算前缀积的同时,记录前缀积末尾 0 的个数。然后,我们可以使用数位 DP 来处理末尾有多少个 0,具体来说,我们可以使用一个二维数组 dp[i][j] 表示考虑到第 i 位,末尾有 j 个 0 的子段数量。转移时,我们可以枚举当前位置的数字,然后统计当前数字对子段末尾 0 的贡献,即当前数字质因子中 2 和 5 的个数,然后将贡献加入 dp 数组中。
最终的答案即为所有以任意位置结尾的子段中符合条件的数量之和。时间复杂度为 O(nlogB),其中 B 为序列中元素的最大值。
以下是修改后的参考代码:
```c++
#include <iostream>
#include <vector>
using namespace std;
const int MAXN = 2e5 + 5;
const int MAXK = 10;
int n, k;
int a[MAXN];
int cnt[MAXK];
int dp[MAXN][MAXK];
int main() {
cin >> n >> k;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
long long ans = 0;
int zero = 0;
for (int l = 1; l <= n; l++) {
// 计算前缀积末尾 0 的个数
if (a[l] == 0) {
zero = 1;
} else if (a[l] % 10 == 0) {
zero++;
} else {
zero = 0;
}
// 重置状态
for (int i = 0; i < k; i++) {
cnt[i] = 0;
}
for (int r = l; r <= n; r++) {
// 计算末尾有 k 个 0 的子段数量
dp[r][0] = 1;
for (int j = 1; j < k; j++) {
dp[r][j] = 0;
}
for (int j = 0; j < k; j++) {
int t = (j + zero) % k;
dp[r][t] += cnt[j];
}
ans += dp[r][k - 1];
// 计算当前数字对子段末尾 0 的贡献
int x = a[r];
int z = zero;
while (x % 10 == 0) {
z++;
x /= 10;
}
cnt[z]++;
}
}
cout << ans << endl;
return 0;
}
```
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)