[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\) 取模后的余数。

  • 输入格式

第一行为两个正整数 \(n\) 和 \(m\) 。

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

第三行为询问数 \(q\) 。

接下来的 \(q\) 行,每一行都有两个正整数,分别为 \(l\) 和 \(r\) 。

  • 输出格式

共 \(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^5\),\(1 \leq m \leq 20\),\(0 \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]\) 中也是同理。

如果这个询问区间跨过了 \(mid\) (\(l \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\) 数组,这样 \(f\) 和 \(g\) 合并就可以得到跨过 \(mid\) 的一段区间的完整的答案了。合并的时候就直接把 \(f\) 中的方案数和 \(g\) 中的方案数相乘即可,即 \([ql, qr]\) 这个询问的答案是 \(\sum\limits_{j+k=m}{f_{qr, j} \times g_{ql, k}}\) 。

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

 

 

 

发表回复

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