给定一个长度为n的正整数序列,a1,a2,a3,......an;现在的任务是要统计子序列的个数, 子序列的条件:长度为k的子序列的和,且该和为7的倍数。 请你计算这样的子序列共有多少个? 输入: 第一行输入n和k (1<=n,k<=200)。 第二行是这n个正整数(都是大于且0小于100的数)。 输出: 输出满足条件的子序列的个数,在1行内输出。 例子输入: 5 3 2 5 4 5 6 例子输出: 1 c++
时间: 2024-03-13 15:43:43 浏览: 358
好的,以下是 C++ 代码实现:
```cpp
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n, k;
cin >> n >> k;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
// 计算前缀和数组
vector<int> prefix_sum(n+1);
for (int i = 0; i < n; i++) {
prefix_sum[i+1] = prefix_sum[i] + a[i];
}
// 统计满足条件的子序列个数
int count = 0;
for (int i = k; i <= n; i++) {
for (int j = i; j <= n; j++) {
if ((prefix_sum[j] - prefix_sum[j-k]) % 7 == 0) {
count++;
}
}
}
cout << count << endl;
return 0;
}
```
与 Python 代码实现类似,我们先读入输入数据,计算出前缀和数组 prefix_sum。然后,我们枚举所有长度为 k 的子序列,计算它们的和,并判断是否为 7 的倍数。具体来说,我们使用两个指针 i 和 j,分别指向子序列的左右端点。通过前缀和数组可以快速计算子序列的和 prefix_sum[j] - prefix_sum[j-k],并判断是否为 7 的倍数。最后,统计满足条件的子序列个数,并输出即可。
阅读全文