题目描述

关系

内容

给定一个长度为 $N$ 的数列，$A_1,A_2,\dots A_N$，如果其中一段连续的子序列 $A_i,A_{i+1},\dots A_j$ 之和是 $K$ 的倍数，我们就称这个区间 $[i,j]$ 是 $K$ 倍区间。

你能求出数列中总共有多少个 $K$ 倍区间吗？

输入格式

第一行包含两个整数 $N$ 和 $K$。

以下 $N$ 行每行包含一个整数 $A_i$。

输出格式

输出一个整数，代表 $K$ 倍区间的数目。

数据范围

$1\le N,K\le 100000$,
$1\le A_i\le 100000$

输入样例：

5 2
1
2
3
4
5

输出样例：

6

问题分析

最初思路

可以利用前缀和在常数时间内求出区间的累加和。

然后感觉就是一个区间 dp 的问题了。我们假设 ${\displaystyle f[i][j]}$ 表示的是区间 ${\displaystyle [i,j]}$ 范围内的所有的 K 倍区间的个数。那么可以很容易的得出下述状态转移方程。

动态规划求解的思路是错误的，因为该题不容许时间复杂度 ${\displaystyle O(n^2)}$ 出现。

但是题目中，没有负数存在，也就是说若区间大小发生变化，有新的数被包括时，区间和一定会变化。

思路分析

首先可以利用前缀和预处理，便于在常数时间内判断是否为 K 区间。

如果枚举 L 和 R 的端点，那么时间复杂度是不允许的（${\displaystyle O(n^2)}$）。还要想办法优化掉一层循环。

for (int r = 1; r <= n; r++) {
	for (int l = 1; l <= r; l++) {
		// calculate
		if ((s[r] - s[l - 1]) % k == 0) res++;
	}
}

要想优化掉一层循环，只能去寻找有没有什么地方出现了重复计算。内层循环的意思是对于确定的右边界 r，有多少个左边界 l 满足 (s[r] - s[l - 1]) % k == 0。即满足 s[r] % k == s[l - 1] % k。

所以，我们可以选择记录所有余数出现的次数，所以我们定义 cnt 数组，cnt[i] 表示余数为 i 的数有多少个。例如，cnt[s[r] % k] 就表示到现在为止有多少个 s[l - 1] % k 的结果为 s[r] % k。也就可以得出答案。

执行流程设计

总结

代码实现

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

typedef long long ll;

const int N = 1e5 + 10;
int n, k;
int cnt[N];
ll s[N];

int main()
{
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        int a;
        cin >> a;
        s[i] = s[i - 1] + a;
    }
    
    ll ans = 0;
    cnt[0] = 1;
    for (int r = 1; r <= n; r++) {
        ans += cnt[s[r] % k];
        cnt[s[r] % k]++;
    }
    cout << ans;
    
    return 0;
}

import java.util.*;
import java.io.*;
import java.math.*;

public class Main {	
	
	final static Re r = new Re();
	final static Wr w = new Wr();
	
	static final int N = 100010;
	static long[] s = new long[N];
	static int[] cnt = new int[N];
	static int n, k;
	
	public static void main(String[] args) throws Exception {
		n = r.nextInt();
		k = r.nextInt();
		for (int i = 1; i <= n; i++) {
			s[i] = r.nextInt();
			s[i] += s[i - 1];
		}
		
		long ans = 0;
		cnt[0] = 1;
		for (int r = 1; r <= n; r++) {
			ans += cnt[(int) (s[r] % k)];
			cnt[(int) (s[r] % k)]++;
		}
		w.print(ans);
		w.close();
	}
	
	
}

class Re {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	StringTokenizer st = new StringTokenizer("");
	
	private String innerNextLine() {
		try {
			return br.readLine();
		} catch (IOException e) {
			e.printStackTrace();
		}
		return null;
	}
	
	public boolean hasNext() {
		while (!st.hasMoreTokens()) {
			String nextLine = innerNextLine();
			if (nextLine == null) {
				return false;
			}
			st = new StringTokenizer(nextLine);
		}
		return true;
	}
	
	
	public String next() {
		hasNext();
		return st.nextToken();
	}
	
	public int nextInt() {
		return Integer.valueOf(next());
	}
}

class Wr {
	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	
	public void print(Object str) throws Exception {
		bw.write(String.valueOf(str) + "");
	} 
	
	public void println(Object str) throws Exception {
		bw.write(String.valueOf(str) + "\n");
	}
	
	public void close() throws Exception {
		bw.close();
	}
}