Processing math: 0%

[2017-2018 Petrozavodsk WC] J. Subsequence Sum Queries

[2017-2018 Petrozavodsk WC] J. Subsequence Sum Queries

时间限制:2000MS 内存限制:262144KB

难度:5.2

  • 题目描述

给定一个长度为 n 的非负整数序列 a 和一个正整数 m

现在有 q 组询问,每组询问给定两个正整数 l, r ,每次可以选择满足 l \leq i \leq r 的若干个 a_i (也可以一个都不选),使得这些 a_i 的和是 m 的非负整数倍,并输出满足条件的选择方案数对 10^9+7 取模后的余数。

  • 输入格式

第一行为两个正整数 nm

第二行为序列 a ,共 n 个元素,用一个空格隔开。

第三行为询问数 q

接下来的 q 行,每一行都有两个正整数,分别为 lr

  • 输出格式

q 行。

i 行为第 i 组询问的答案。

  • 样例输入

  • 样例输出

  • 样例说明

对于第一组询问 l=1, r=2 ,有 不选、选择 5, 1 ,共 2 种情况。

对于第二组询问 l=1, r=3 ,有 不选、选择 5, 1 、选择 5, 1, 3 、选择 3 ,共 4 种情况。

对于第三组询问 l=1, r=4 ,有 不选、选择 5, 1 、选择 5, 1, 3 、选择 3 、选择 1, 2 、选择 1, 3, 2 ,共 6 种情况。

对于第四组询问 l=2, r=4 ,有 不选、选择 3 、选择 1, 2 、选择 1, 3, 2 ,共 4 种情况。

  • 数据范围

对于 10\% 的数据,有 1 \leq n, q \leq 10

对于 40\% 的数据,有 1 \leq n, q \leq 1000

对于 100\% 的数据,有 1 \leq n, q \leq 2 \times 10^51 \leq m \leq 200 \leq a_i \leq 10^9

保证每组询问的 l, r 满足 1 \leq l \leq r \leq n

 

 

YZOJ P4199

Source: [2017-2018 Petrozavodsk Winter Training Camp, Saratov SU Contest] J. Subsequence Sum Queries


 

 

 

(注:以下的取模操作均在非负整数意义下。)

最暴力的做法就是对于每一个询问的区间暴力做一遍背包计数,容量就变成 \bmod m 的余数 0 ~ (m-1) 了。转移就是 \(f_{i, j}=f_{i-1, j}+f_{i-1, (j-a_i)\%m}\) ,表示 a_i 不选和选的情况数之和。这样的复杂度可以达到 O(nmq) 是无法承受的。

还可以想到线段树进行背包合并,但是这样的复杂度为 O((n+q)m^2logn) ,会 TLE

所以想到进行分治。(以下所有 mid=\lfloor\frac{l+r}{2}\rfloor

首先离线处理询问,然后考虑区间 [l, r] 如何对这个询问产生贡献。首先,如果这个询问区间完全在 [l, mid-1] 中,那么先不用处理它,在递归进 [l, mid-1] 时处理就好了(注意,区间端点 =mid 的会在下面进行处理)。同样如果这个询问区间完全在 [mid+1, r] 中也是同理。

如果这个询问区间跨过了 midl \leq ql \leq mid \leq qr \leq r),那么这个询问的答案就可以被处理出来。注意因为 [l, r] 被分割成了 [l, mid][mid+1, r] 这两个子区间,所以询问区间 [ql, qr] 也可以被分割成两个子区间 [ql, mid][mid+1, qr] 。要快速的合并,所以对 [mid+1, r] 中的元素做一遍正向DP设得到 f 数组,对 [l, mid] 中的元素做一遍反向DP设得到 g 数组,这样 fg 合并就可以得到跨过 mid 的一段区间的完整的答案了。合并的时候就直接把 f 中的方案数和 g 中的方案数相乘即可,即 [ql, qr] 这个询问的答案是 \sum\limits_{j+k=m}{f_{qr, j} \times g_{ql, k}}

这样处理下去,时间复杂度只有 O(m(nlogn+q)) 足以通过本题。

 

 

 

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注