题目分析

我们需要统计给定序列中所有连续子序列的和能被 $d$ 整除的数量。连续子序列的和可以通过前缀和来高效计算。

解题思路

1. 前缀和与模运算：计算序列的前缀和数组 $sum$，其中 $sum[i]$ 表示前 $i$ 个元素的和模 $d$ 的结果。这样可以将问题转化为统计 $sum$ 数组中相同余数的出现次数。
2. 余数统计：使用数组 $r$ 记录每个余数出现的次数。初始时，$r[0] = 1$，因为空子序列的和为 $0$，模 $d$ 也为 $0$。
3. 组合计数：对于每个余数 $i$，如果有 $r[i] \geq 2$，则这些余数对应的位置可以两两组合形成满足条件的子序列。组合数为 $\binom{r[i]}{2} = \frac{r[i] \times (r[i] - 1)}{2}$。

关键公式

• 前缀和模运算：$sum[i] = (sum[i - 1] + a[i]) \mod d$
• 组合数计算：$\binom{r[i]}{2} = \frac{r[i] \times (r[i] - 1)}{2}$

方法步骤

1. 输入处理：读取测试用例数量 $c$，每个测试用例的除数 $d$ 和序列长度 $n$，以及序列元素。
2. 计算前缀和模 $d$：初始化 $sum$ 数组并计算每个位置的前缀和模 $d$。
3. 统计余数出现次数：使用数组 $r$ 记录每个余数的出现次数。
4. 计算满足条件的子序列数量：遍历余数数组 $r$，计算所有可能的组合数并累加。
5. 输出结果：打印每个测试用例的结果。

该方法通过前缀和和模运算将问题转化为组合计数问题，时间复杂度为 $O(n + d)$，适用于大规模数据。

#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;

const int MAXN = 50005;
int a[MAXN];
int sum[MAXN];
const int MAXD = 1000005;
int r[MAXD];
int c, ci;
int d, n;
long long int res;

int main()
{
	int i;
	
	while (scanf("%d", &c) == 1) {
		for (ci = 0; ci < c; ++ci) {
			scanf("%d%d", &d, &n);
			for (i = 0; i < n; ++i) {
				scanf("%d", &a[i]);
				a[i] = a[i] % d;
				sum[i] = 0;
			}
			memset(r, 0, MAXD * sizeof(int));
			sum[0] = a[0];
			for (i = 1; i < n; ++i) {
				sum[i] = (sum[i - 1] + a[i]) % d;
			}
			
			++r[0];
			for (i = 0; i < n; ++i) {
				++r[sum[i]];
			}
			
			res = 0;
			for (i = 0; i < d; ++i) {
				if (r[i] >= 2) {
					res += 1LL * r[i] * (r[i] - 1) / 2;
				}
			}
			
			printf("%lld\n", res);
		}
	}
	
	return 0;
}