[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))\) 足以通过本题。