题目内容

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

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

题面描述

给定一个整数序列 $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$ 的子数组数量。