1000ms

Difficulty: 5

所属公司 : 中国电信

时间 :2024年10月26日场

算法与标签>双指针

会员或题库专享

请先，开通会员或购买题库中国电信编程题库，可解锁完整内容。

购买中国电信编程题库开通会员

会员专享

请先登录，登录后可使用今日免费解锁；开通会员，或购买该题目所属题库（中国电信编程题库），可解锁完整内容。

购买题库开通会员

题面描述

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