题面描述

给定一个整数序列 $a$ ，以及两个整数 $x$ 和 $k$ 。

求出有多少个区间 $[L, R]$ （ $L \leq R$ ），使得该区间中恰好有 $k$ 个 $a_i$ （ $L \leq i \leq R$ ）满足 $a_i$ 能被 $x$ 整除。

思路

双指针，计算“至多有 $k$ 个 $1$ ”的子数组数量，再减去“至多有 $k-1$ 个 $1$ ”的子数组数量，即得到恰好有 $k$ 个 $1$ 的子数组数量。

1000ms

Difficulty: 5

算法与标签>双指针

给定一个整数序列 $a$ ，以及 $2$ 个整数 $x$ ， $k$ 。

求出有多少区间 $[L, R](L <= R)$ ，使得该区间中恰好有 $k$ 个 $a_i(L <= i <= R)$ 满足 $a_i$ 能被 $x$ 整除。

时间限制：1000ms

内存限制：262mb

$1 <= length(a), x <= 10^5$ $0 <= k <= 10^5$

返回答案

输入

1 2 3 4
2 1

输出

说明

总共有 $6$ 个区间，满足恰好有 $1$ 个数被 $2$ 整除。

$[1,2],[1,3],[2,2],[2,3],[3,4],[4,4]$ 。

输入

预期输出（选填）