题面描述

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

题目内容

给定一个整数序列 $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

输入

1 2 3 4
2 1

输出

6

说明

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

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